Kelas kompleksitas terdiri dari masalah-masalah yang dapat diputuskan oleh mesin Turing waktu polinomial nondeterministic yang memiliki paling banyak satu yang menerima jalur komputasi. Artinya, solusinya, jika ada, unik dalam pengertian ini. Diperkirakan sangat tidak mungkin bahwa semua masalah...
The Valiant-Vazirani teorema mengatakan bahwa jika ada algoritma waktu polinomial (deterministik atau acak) untuk membedakan antara formula SAT yang memiliki tepat satu tugas memuaskan, dan formula unsatisfiable - maka NP = RP . Teorema ini dibuktikan dengan menunjukkan bahwa UNIQUE-SAT adalah NP...
Pertimbangkan masalah berikut: diberikan formula CNF dan tugas yang memenuhi formula ini, adakah tugas lain yang memuaskan untuk formula ini? Apa kompleksitas masalah ini? (Ini pasti di NP, tetapi juga NP-keras?) Bagaimana jika Anda tidak diberi tugas dan Anda hanya ingin memutuskan apakah...
EDIT di 2011/02/08: Setelah beberapa referensi menemukan dan membaca, saya memutuskan untuk memisahkan pertanyaan asli menjadi dua yang terpisah. Inilah bagian tentang UP vs NP, untuk bagian kelas sintaksis dan semantik silakan lihat Manfaat untuk kelas sintaksis dan semantik . U PUP\mathsf{UP}...
Saya mencari tahu apakah ada hasil umum tentang atau contoh tentang kelengkapan NP dari masalah menemukan solusi kedua untuk masalah NP-lengkap. Lebih tepatnya, saya tertarik dengan masalah apa pun dari formulir berikut: Diberikan solusi untuk contoh dari masalah NP-complete, apakah ada solusi...
Mengikuti saran Josh Grochow, saya mengubah komentar saya dari pertanyaan sebelumnya menjadi pertanyaan baru. Bukti apa yang kita miliki untuk ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Berikut UPUP\mathsf{UP} adalah kelas bahasa dikenali oleh waktu non-deterministik mesin Turing polinomial yang...
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 baru-baru ini membaca makalah yang sangat bagus oleh Valiant dan Vazirani yang menunjukkan bahwa jika , maka tidak akan ada algoritma yang efisien untuk menyelesaikan SAT bahkan di bawah janji bahwa itu tidak memuaskan atau memiliki solusi yang unik. Dengan demikian menunjukkan bahwa SAT tidak...
Masalah " kedua " adalah masalah menentukan keberadaan solusi lain yang berbeda dari beberapa solusi yang diberikan misalnya masalah.XXX Untuk beberapa masalah -complete, versi solusi kedua adalah N P -complete (memutuskan keberadaan solusi lain untuk masalah penyelesaian persegi Latin parsial)...