Pertanyaan ini terkait erat dengan posting lain: Fase Transisi dalam Masalah Keras NP tetapi agak berbeda. Sementara pertanyaan itu adalah tentang kekerasan dari kasus-kasus khusus masalah sulit NP, ini adalah tentang peringkat kesulitan dari kasus yang sama. Ada banyak bibliografi tentang efek...
Bahasa sehari-hari, definisi eksponen matriks-perkalian ωω\omega adalah nilai terkecil yang ada algoritma perkalian-matriks nωnωn^{\omega} . Ini tidak dapat diterima sebagai definisi matematika formal, jadi saya kira definisi teknis adalah sesuatu seperti infimum atas semua ttt seperti bahwa ada...
Q1. Kapan kita dapat mengatakan bahwa dua program (ditulis dalam beberapa bahasa pemrograman seperti C ++) berbeda? Ekstrem pertama adalah untuk mengatakan bahwa dua program adalah setara jika mereka identik. Ekstrem lainnya adalah dengan mengatakan dua program setara jika mereka menghitung fungsi...
Pertimbangkan masalah berikut: Input : hyperplane H = { y ∈ R n : a T y = b }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , diberikan oleh vektor dan dalam representasi biner standar .a ∈ Z na∈Zn\mathbf{a} \in \mathbb{Z}^n b ∈ Zb∈Zb \in \mathbb{Z} Output :x ∈ Z...
Apa beberapa masalah non-sepele di mana kita tahu algoritma saat ini yang kita miliki adalah yang optimal asimptotik? (Untuk mesin turing) Dan bagaimana ini
Pembukaan. Kelas kompleksitas AM adalah masalah-masalah yang dapat diselesaikan dengan sistem bukti interaktif dua putaran antara prover "Merlin" dan verifier "Arthur". Masalah - yang menguji beberapa properti dari objek X - adalah pada AM jika: Untuk contoh YA , untuk pesan "tantangan" acak...
Saya telah mencari formalisasi teorema kekompakan untuk FOL, tetapi belum menemukannya. Adakah yang tahu tentang perkembangan semacam itu atau pekerjaan
Aljabar Boolean dapat diekspresikan dalam kalkulus lambda yang tidak diketik dalam (misalnya) dengan cara ini. true = \t. \f. t; false = \t. \f. t; not = \x. x false true; and = \x. \y. x y false; or = \x. \y. x true y; Aljabar boolean juga dapat dikodekan dalam Sistem F dengan cara ini : CBool...
The 1-dim algoritma Weisfeiler-Lehman (WL) umumnya dikenal sebagai label kanonik atau algoritma warna perbaikan. Ia bekerja sebagai berikut: Pewarnaan awal seragam, untuk semua simpul .C0C0C_0C0( v ) = 1C0(v)=1C_0(v) = 1v ∈ V( G ) ∪ V( H)v∈V(G)∪V(H)v \in V (G) \cup V (H) Dalam putaran st, warna C...
Dalam perspektif bahasa pemrograman, apa yang dimaksud dengan subtyping? Saya mendengar bahwa "Warisan bukan Subtipe". Lalu apa perbedaan antara pewarisan dan
Ada sejumlah algoritma dan struktur data yang mengeksploitasi gagasan bahwa mendapatkan nilai minimumnya di k = \ sqrt n . Contoh umum termasukmax{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n algoritma langkah-langkah raksasa-langkah untuk menghitung logaritma diskrit di...
Grafik planar adalah -gratis. Grafik tersebut dapat didekomposisi menjadi komponen tri-terhubung, yang dikenal sebagai komponen planar atau .K3 , 3K3,3K_{3,3}K5K5K_5 Apakah ada dekomposisi grafik genus satu yang "bagus"? Dalam karya seminal mereka pada grafik anak di bawah umur, Roberston dan...
Grafik yang terhubung dapat didekomposisi menjadi komponen-komponen yang tidak terhubung. Ini pohon blok batasTLC unik. Demikian pula, grafik yang terhubung dua kali lipat dapat didekomposisi menjadi komponen-komponen yang tidak terhubung. Pohon SPQR yang sesuai menjelaskan semua potongan 2-simpul...
Pemecah SAT memberikan cara yang ampuh untuk memeriksa validitas rumus boolean dengan satu quantifier. Misalnya, untuk memeriksa validitas ∃x.φ(x)∃x.φ(x)\exists x . \varphi(x) , kita dapat menggunakan pemecah SAT untuk menentukan apakah φ(x)φ(x)\varphi(x) memuaskan. Untuk memeriksa validitas...
Dalam menerapkan filter Bloom, pendekatan tradisional membutuhkan beberapa fungsi hash independen. Kirsch dan Mitzenmacher menunjukkan bahwa Anda sebenarnya hanya membutuhkan dua, dan dapat menghasilkan sisanya sebagai kombinasi liniernya. Pertanyaan saya adalah: apa, sungguh, perbedaan antara dua...
Untuk penyisipan planar grafik planar pada bidang dengan tepi lurus, tentukan simpul sebagai simpul tajam jika sudut maksimum antara dua tepi berturut-turut di sekitarnya adalah lebih dari 180. Atau dengan kata lain, jika ada garis yang melewatinya vertex di embedding sedemikian rupa sehingga semua...
Apakah ada paket perangkat lunak yang memungkinkan dekomposisi unitari dari ke dalam sirkuit kuantum melalui set gerbang universal yang telah ditentukan sebelumnya?U(
Saya baru-baru ini menjadi sangat tertarik pada parametrikitas setelah melihat makalah LICS Bernardy and Moulin 2012 ( https://dl.acm.org/citation.cfm?id=2359499 ). Dalam makalah ini, mereka menginternalisasi parametrisitas unary dalam sistem tipe murni dengan tipe dependen dan memberi petunjuk...
Pertimbangkan masalah berikut: Diberikan grafik kueri G=(V,E)G=(V,E)G = (V, E) dan grafik referensi , kami ingin menemukan pemetaan injeksi yang meminimalkan jumlah ujung-ujungnya ( v 1 , v 2 ) ∈ E sedemikian sehingga ( f ( v 1 ) , f ( v 2 ) ) ∉ E ′ . Ini adalah generalisasi dari masalah...
Diberikan himpunan dan B , hubungan difungsional ( ∼ ) ⊆ A × B di antara mereka didefinisikan sebagai hubungan yang memuaskan properti berikut:SEBUAHSEBUAHABBB ( ∼ ) ⊆ A × B(∼)⊆SEBUAH×B(\sim) \subseteq A \times B Jika dan a ′ ∼ b ′ dan a ∼ b ′ , maka a ′ ∼ b . a ∼ bSebuah∼ba \sim bSebuah′∼...