Pertanyaan saya adalah mengapa batas bawah untuk kedalaman 3 sirkuit Boolean dengan gerbang "dan" dan "xor" untuk determinan tidak menyiratkan batas bawah yang sama untuk sirkuit aritmatika di atas ZZ\mathbb{Z} ? Apa yang salah dengan argumen berikut: Misalkan CCC menjadi rangkaian penentu...
Saya mencari referensi tentang kompleksitas masalah penyeimbangan rumus Boolean . Khususnya, Apakah diketahui bahwa rumus Boolean dapat diseimbangkan dalam ?AC0AC0\mathsf{AC^0} Apakah ada bukti sederhana keseimbangan Boolean yang menyeimbangkan berada di ?AC0AC0\mathsf{AC^0} Maksud "sederhana"...
Biarkan kelas BPNC (kombinasi dan ) menjadi algoritma paralel kedalaman log dengan probabilitas kesalahan terbatas dan akses ke sumber acak (saya tidak yakin apakah ini memiliki nama yang berbeda). Tentukan kelas DBPNC dengan cara yang sama, kecuali bahwa semua proses memiliki akses acak ke aliran...
Dalam sebuah pembicaraan oleh Razborov, sebuah pernyataan kecil yang aneh diposting. Jika FACTORING sulit, maka teorema kecil Fermat tidak dapat dibuktikan dalam .S12S21S_{2}^{1} Apa itu dan mengapa bukti saat ini tidak ada di ? S 1
BPPBPP\mathsf{BPP} danZPPZPP\mathsf{ZPP} adalah dua kelas kompleksitas probabilistik dasar. BPPBPP\mathsf{BPP} adalah kelas bahasa yang diputuskan oleh algoritma Turing polinomial-waktu probabilistik di mana probabilitas algoritma mengembalikan jawaban yang salah dibatasi, yaitu probabilitas...
Dalam kompleksitas komunikasi, dugaan log-rank menyatakan hal itu cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Di mana adalah kompleksitas komunikasi M ( x , y ) dan r k ( M ) adalah pangkat M (sebagai matriks) atas
Kelas kompleksitas didefinisikan sebagai berikut (dari Wikipedia ):SP2S2P\textrm{S}_2^\textrm{P} Bahasa adalah dalam S P 2 jika ada predikat polinomial-waktu P sedemikian rupaL.L.LSP2S2PS_2^PPPP Jika , maka ada y sedemikian rupa sehingga untuk semua z , P ( x , y , z ) = 1x ∈ Lx∈L.x \in...
Apakah grafik isomorfisme (masalah keputusan) dalam ? Berikut U P adalah kelas masalah keputusan diterima oleh mesin Turing ambigu (lihat kebun binatang kompleksitas ).UP∩coUPUP∩coUP\mathsf{UP}\cap
Saya mencoba memahami kelas-kelas ini tetapi selalu bingung ... pertanyaannya adalah: Apa hubungan antara dan # P , khususnya apakah ini merupakan pertanyaan terbuka?FNPFNPFNP#P#P\#P Apa hubungan dan N P ? apakah pertanyaan ini terbuka?⊕P⊕P\oplus PNPNPNP Bagaimana dengan hubungan antara dan P F...
Pohon rentang dari suatu grafik disebut pohon kelengkapan jika rangkaian daunnya menginduksi subgraf lengkap dalam grafik host. Diberikan grafik dan bilangan k k , apa kompleksitas memutuskan jika G berisi pohon kelengkapan dengan paling banyak k daun?GGGkkkGGGkkk Alasan untuk mengajukan...
Mengingat satu set poin di ruang Euclides dimensi, masalahnya adalah untuk menentukan apakah convex hull berisi bola Unit berpusat pada titik asal.nnnddd Apakah masalah ini dalam NP? Itu dalam co-NP karena orang dapat memberikan titik di bola di luar lambung cembung sebagai saksi dan...
Saya memiliki masalah berikut: Input: dua set interval dan T (semua titik akhir adalah bilangan bulat). Pertanyaan: adakah bijih monoton f : S → T ?SSSTTTf: S→ Tf:S→Tf:S \to T Bijection adalah monoton wrt set masuknya order pada dan T . ∀ X ⊆ Y ∈ S , f ( X ) ⊆ f ( Y )SSSTTT∀ X⊆ Y∈ S, f ( X) ⊆ f(...
Jika kita dapat membuktikan bahwa , apakah itu menyiratkan bahwa ?L = PL.=P\mathsf{L}=\mathsf{P}N L = N PNL.=NP\mathsf{NL}=\mathsf{NP} Saya pikir itu masalahnya, tapi saya tidak bisa membuktikannya (juga untuk yang
Diberikan grafik terarah, kami ingin memutuskan apakah itu berisi siklus terarah dengan panjang genap. Makalah tahun 1997 oleh YUSTER dan ZWICK ini menyatakan bahwa masalahnya tidak diketahui dalam dan juga tidak diketahui lengkap.PPPNPNPNP Apakah ada hasil terbaru yang menyelesaikan...
Saya menemukan masalah terbuka yang diajukan oleh David Eppstein dan saya tertarik dengan status kompleksitasnya. Dia menduga itu NP-lengkap. Input: oleh n matriks 0's dan 1's, urutan n 2 0's dan 1'snnnnnnn2n2n^2 Pertanyaan: Apakah ada jalur melalui entri matriks yang berdekatan, yang mencakup...
Mari kita sebut bahasa NP yang jarang memiliki sertifikat jika dan hanya jika:L ∈L∈L \in Ada polinomial sedemikian rupa sehingga untuk setiap input ukuran , jika maka set sertifikat yang memverifikasi bahwa berukuran polinomially, yaitu . x ∈ Σ ∗ n x ∈ L U x u x ∈ L | U x | ≤ p ( n )p : N →...
Apa definisi standar Planar 3-SAT? Saya telah melihat sejumlah definisi berbeda. Apa kertas asli yang mendefinisikannya dan membuktikannya sebagai
Dalam Topik Lanjutan dalam Jenis dan Bahasa Pemrograman disebutkan, dalam bab tentang sistem tipe sub-struktural, bahwa kalkulus affine lambda "dibuat dengan hati-hati" dengan kombinator rekursi untuk daftar hanya dapat mengetik istilah yang memiliki waktu berjalan polinomial (tidak menyajikan...
Apakah ada masalah yang dapat dipecahkan dalam waktu polinomial hanya jika P! = NP, dan sebaliknya dipecahkan dalam waktu (katakanlah) waktu?O ( 2n)O(2n)O(2^n) Contoh sederhana adalah: Jika P! = NP, hitung tes primality untuk angka n-bit acak, jika tidak, evaluasi posisi kasus terburuk acak dalam...
Menggunakan model real-RAM / BSS, kami memiliki kelas NP R , (di mana BSS adalah model Blum-Shub-Smale komputer dengan operasi lebih dari real). Kami memiliki masalah lengkap NP R. Jadi, pertanyaannya adalah adakah analog dugaan Berman Hartmanis untuk kelas NP R ? Tentu saja, pertanyaan yang...