Bukti yang dapat diperiksa secara probabilistik
Saya akrab dengan banyak hasil yang menggunakan teorema PCP (terutama dalam algoritma perkiraan), tetapi saya tidak pernah menemukan penjelasan yang jelas tentang teorema PCP (yaitu, bahwa ).N P = P C P (O(log( n ) ) , O ( 1 ) )NP=PCP(O(log(n)),O(1))\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1)) Apa...
Misalkan dan adalah dua grafik tidak berarah pada set simpul . isomorfik jika dan hanya jika ada permutasi sedemikian sehingga , atau lebih resmi, jika ada permutasi sedemikian sehingga adalah ujung dalam jika dan hanya jika adalah keunggulan dalam . Masalah Grafik Isomorfisme adalah masalah...
Aplikasi penting dari teorema PCP adalah bahwa ia menghasilkan hasil jenis "kekerasan perkiraan". Dalam beberapa kasus yang relatif lebih sederhana seseorang dapat membuktikan kekerasan seperti itu tanpa PCP. Namun, adakah kasus di mana kekerasan hasil perkiraan pertama kali terbukti menggunakan...
Negara-negara PCP teorema bahwa tidak ada algoritma waktu polinomial untuk MAX 3SAT untuk menemukan tugas memuaskan klausul formula 3SAT satisfiable kecuali P = N P .7 / 8 + ε7/8+ϵ7/8+ \epsilonP= NPP=NPP = NP Ada sepele polinomial waktu algoritma yang memenuhi dari klausa. Jadi, bisa kita lakukan...
bagaimana seseorang dapat menunjukkan bahwa apa hubungan antara "dugaan game unik" dan "teorema PCP"? bagaimana orang menjelaskan "Dugaan game unik" adalah bentuk yang lebih kuat dari "teorema
Masalah pemeliharaan pesanan (atau "mempertahankan pesanan dalam daftar") adalah untuk mendukung operasi: singleton: membuat daftar dengan satu item, mengembalikan pointer ke sana insertAfter: diberi pointer ke item, memasukkan item baru setelahnya, mengembalikan pointer ke item baru delete:...
Sistem bukti probabilistik umumnya disebut sebagai pembatasan , di mana Arthur hanya dapat menggunakan bit acak dan hanya dapat memeriksa bit sertifikat bukti yang dikirim oleh Merlin (lihat, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).M A f ( n ) g ( n )PCP[ f( n ) , g( n )...
Raz Paralel pretition teorema adalah hasil yang penting dalam PCP, inapproximation, dll Teorema ini fomalized sebagai berikut. G=(S,T,A,B,π,V)G=(S,T,A,B,π,V)G=(\mathcal{S},\mathcal{T},\mathcal{A},\mathcal{B},\pi,
Formulasi setara PCP teorema adalah: Untuk Max 3-SAT itu adalah -Hard untuk membedakan antara formula satisfiable dan formula mana paling r -fraction klausul yang satisfiable (untuk beberapa r < 1 ).NPNPNPrrrr<1r<1r\lt 1 Apakah ada teorema dikotomi diketahui yang mengklasifikasikan...
Saya membaca buktinya dari sini dan saya menemukan masalah teknis (yang sangat penting). Saya tahu ini agak spesifik dan konteksnya bermasalah, tetapi saya sendiri tidak bisa memahaminya. Di halaman 51 dan 55, setelah menyajikan verifier "standar", mereka beralih untuk memodifikasi verifier untuk...
Berikut ini mungkin tampak bodoh (dan itu mungkin mencerminkan pemahaman saya yang buruk - jadi tolong tahan dengan saya) Saya punya pertanyaan tentang teorema PCP. Kita tahu bahwa setelah tiga langkah pertama yaitu. Pengurangan Gelar, Ekspanderisasi dan Penguatan Gap, kami memiliki grafik kendala...
Dalam kebanyakan sistem bukti probabilistik (teorema PCP, misalnya), probabilitas kesalahan biasanya didefinisikan pada sisi false-positive, yaitu definisi tipikal dapat terlihat seperti: jika maka verifier selalu menerima, tetapi dalam kasus lain kemungkinan penolakan setidaknya 1/2.x ∈ Lx∈Lx \in...
Buku karya Arora dan Barak berisi dalam bab catatan tentang PCP Kami mencatat bahwa strategi umum Dinur agak mengingatkan pada konstruksi zig-zag grafik expander dan algoritme logspace deterministik Reingold untuk konektivitas tidak terarah yang dijelaskan dalam Bab 20, yang menunjukkan bahwa...
Teorema PCP menyatakan bahwa setiap masalah keputusan dalam NP memiliki bukti probabilistically checkable (atau setara, bahwa ada sistem bukti yang lengkap dan quasi-sound untuk teorema di NP menggunakan kompleksitas kueri konstan dan bit acak secara logaritmik). "Kebijaksanaan rakyat" yang...
Saya sedang mempelajari Konjektur Game Unik dan pengurangan terkenal untuk Max-Cut dari Khot et al. Dari makalah mereka dan di tempat lain di internet, sebagian besar penulis menggunakan (apa yang bagi saya adalah) kesetaraan implisit antara pengurangan MAX-CUT dan membangun tes khusus untuk kode...
Apa batas atas asimptotik yang paling dikenal pada ukuran bukti yang dapat diperiksa secara probabilistik? Idealnya, saya mencari survei kontemporer tentang pertanyaan luas ini, tetapi jika tidak ada, saya terutama tertarik pada ketidak-taksiran 3-SAT. Misalkan 7/8 + ε-3-SAT menjadi 3-SAT dengan...
Pada langkah reduksi derajat dari bukti Dinur, grafik input ditransformasikan menjadi grafik G ′ dengan mengganti setiap simpul v ∈ V ( G ) dengan seperangkat simpul, c l o u d ( v ) , sedemikian rupa sehingga | c l o u d ( v ) | = d e g r e e G ( v ) , dan memaksakan derajat d grafik expander pada...