Apakah masalah -complete secara inheren kurang dapat ditelusuri dibandingkan masalah -complete?

Saat ini, menyelesaikan masalah lengkap atau masalah lengkap tidak layak dalam kasus umum untuk input besar. Namun, keduanya dapat dipecahkan dalam waktu eksponensial dan ruang polinomial.$NP$$PSPACE$

Karena kami tidak dapat membuat komputer nondeterministic atau 'beruntung', apakah ada bedanya bagi kami jika masalahnya -complete atau -complete?$NP$$PSPACE$

Ini adalah pertanyaan yang sangat bagus yang sering saya pikirkan: Apakah fakta bahwa suatu masalah adalah -complete atau -complete benar-benar memengaruhi kompleksitas waktu terburuk dari masalah? P S P A C $NP$$PSPACE$Yang lebih kabur, apakah perbedaan seperti itu benar-benar memengaruhi kerumitan "kasus tipikal" dalam praktik?

Intuition mengatakan bahwa masalah -complete lebih sulit daripada -complete, terlepas dari ukuran kompleksitas yang Anda gunakan. Tetapi situasinya halus. Bisa jadi, misalnya, bahwa (Kuantitatif Boolean Rumus, masalah kanonik lengkap) berada dalam waktu subeksponensial jika dan hanya jika (Kepuasan, masalah kanonik lengkap) dalam waktu subeksponensial. (Satu arah jelas; arah lainnya akan menjadi hasil utama!) Jika ini benar, maka mungkin dari sudut pandang "Saya hanya ingin menyelesaikan masalah ini", bukan masalah besar apakah masalahnya -lengkap atauN P Q B F P S P A C E S A T N P P S P A C E N $PSPACE$$NP$$QBF$$PSPACE$$SAT$$NP$$PSPACE$$NP$-complete: salah satu cara, algoritma subexponential untuk satu menyiratkan algoritma subexponential untuk yang lain.

Biarkan saya menjadi pendukung iblis, dan berikan Anda sebuah contoh di mana satu masalah menjadi "lebih sulit" daripada yang lain, tetapi ternyata juga "lebih bisa ditelusuri" daripada yang lain juga.

Biarkan menjadi rumus Boolean pada variabel , di mana adalah genap. Misalkan Anda memiliki pilihan antara dua rumus yang ingin Anda putuskan:n $F(x_1,\ldots,x_{n})$$n$$n$

$\Phi_1 = (\exists x_1)(\exists x_2)\cdots (\exists x_{n-1})(\exists x_{n})F(x_1,\ldots,x_{n})$ .

$\Phi_2 = (\exists x_1)(\forall x_2)\cdots (\exists x_{n-1}(\forall x_{n})F(x_1,\ldots,x_{n})$

(Yaitu, di , bilangan alternatif berganti.)$\Phi_2$

Mana yang menurut Anda lebih mudah untuk dipecahkan? Rumus tipe , atau rumus tipe ?$\Phi_1$$\Phi_2$

Satu akan berpikir bahwa pilihan yang jelas adalah , karena hanya -Lengkap untuk memutuskan itu, sedangkan adalah masalah -Lengkap. Namun pada kenyataannya, menurut algoritma kami yang paling terkenal, adalah masalah yang lebih mudah. Kami tidak tahu bagaimana menyelesaikan untuk umum dalam waktu kurang dari langkah. (Jika kita bisa melakukan ini, kita akan memiliki batas formula ukuran baru yang lebih rendah!) Tetapi dapat dengan mudah diselesaikan untuk setiap dalam waktu acak , menggunakan pencarian pohon permainan acak! Untuk referensi, lihat Bab 2, Bagian 2.1, di Motwani dan Raghavan. N P Φ 2 P S P A C E Φ 2 Φ 1 F 2 n Φ 2 F O ( 2, 793 n$\Phi_1$$NP$$\Phi_2$$PSPACE$$\Phi_2$$\Phi_1$$F$$2^n$$\Phi_2$$F$$O(2^{.793 n})$

Intinya adalah bahwa menambahkan penjumlahan universal sebenarnya membatasi masalah , membuatnya lebih mudah untuk dipecahkan, daripada lebih sulit. Algoritma pencarian tree game sangat bergantung pada memiliki bilangan kuantifikasi, dan tidak dapat menangani kuantifikasi arbitrer. Namun, intinya tetap bahwa masalah kadang-kadang bisa "lebih sederhana" di bawah satu ukuran kompleksitas, meskipun mereka mungkin terlihat "lebih keras" di bawah ukuran lain.

Itu penting, karena ada lebih banyak yang dipertaruhkan daripada apakah kita dapat menemukan solusi atau tidak. Yang juga menarik adalah apakah kami dapat memverifikasi solusi. Perbedaan kualitatif lainnya dapat dibuat antara kesulitan masalah, tetapi untuk NP versus kelas kompleksitas yang lebih besar, ini akan menjadi yang saya identifikasi sebagai yang paling penting.

Untuk masalah keputusan - masalah yang setiap contohnya memiliki jawaban ' YA ' atau ' TIDAK ' - NP justru merupakan kelas masalah yang kami dapat secara efisien memverifikasi bukti yang diakui bahwa contoh yang diberikan adalah contoh ' YA ', secara deterministik, jika kami disajikan dengan satu. Misalnya, jika Anda memiliki tugas variabel yang memuaskan untuk instance 3-SAT, tugas itu memungkinkan Anda untuk secara efisien membuktikan bahwa instance tersebut memuaskan. Tugas yang memuaskan seperti itu mungkin sulit ditemukan, tetapi begitu Anda memilikinya, Anda dapat dengan mudah membuktikan kepada orang lain bahwa instance tersebut memuaskan hanya dengan meminta mereka memverifikasi solusi yang Anda temukan.

Demikian pula, untuk TNP , ada bukti yang dapat diperiksa secara efisien untuk contoh ' TIDAK '; dan untuk masalah dalam NP  ∩  coNP , Anda dapat melakukan keduanya. Tetapi untuk masalah PSPACE -complete, tidak ada prosedur seperti itu ada - kecuali Anda dapat membuktikan beberapa persamaan kelas kompleksitas yang cukup spektakuler.

Kami tidak tahu bagaimana membangun masalah hard case rata-rata dari (NP terburuk) menyelesaikan masalah tapi kami bisa melakukan ini untuk PSPACE (lihat Köbler & Schuler (1998) ) untuk menciptakan masalah bahkan pada distribusi seragam yang tidak dapat diselesaikan pada sebagian besar input kecuali semua PSPACE mudah dihitung.

Dari sisi praktis, penting untuk diingat bahwa NP-Completeness bukan penghalang bagi banyak masalah dalam praktiknya. Alat kembar pemecah SAT dan CPLEX (untuk pemrograman linier bilangan bulat) cukup kuat dan cukup direkayasa dengan baik sehingga sering kali mungkin untuk memecahkan contoh besar masalah NP-lengkap dengan membingkai masalah sebagai ILP yang sesuai atau dengan mengurangi menjadi SAT.

Saya tidak mengetahui solver yang direkayasa dengan baik untuk masalah di PSPACE.

Anda mungkin berpikir seperti ini: apakah masalah matematika memiliki bukti yang dapat dibaca manusia, atau apakah secara inheren memerlukan "bukti komputer." Contoh: apakah posisi awal checker seri? (Jawab: ya.) Apakah posisi awal catur menang untuk orang kulit putih? (Jawab: tidak diketahui, tetapi sebagian besar lulusan sekolah berpendapat bahwa ini adalah seri.)

Bukti bahwa posisi awal checker adalah hasil imbang pada akhirnya mengharuskan seseorang untuk menerima bahwa komputer benar-benar memverifikasi banyak kasus khusus secara akurat. Jika bukti tentang catur pernah ada, mungkin akan membutuhkan pembaca manusia untuk menerima bahwa komputer diverifikasi dengan benar bahkan lebih banyak kasus khusus. Dan mungkin tidak ada metode yang lebih pendek untuk membuktikan pernyataan tersebut. Itu adalah masalah di PSPACE. Jika suatu masalah "hanya" dalam NP, maka (secara intuitif) manusia bisa memegang seluruh bukti di kepalanya. Manusia itu mungkin perlu menjadi ahli matematika yang sangat terspesialisasi, tentu saja.

Metafora ini akan rusak jika didorong terlalu keras - NP-proof ukuran mungkin tidak akan pernah bisa masuk ke kepala siapa pun. Tetapi gagasan dasar bahwa "saksi itu kecil" adalah bagian dari alasan mengapa masalah NP-lengkap memiliki begitu banyak arti penting industri.$n^{1000000}$

Lebih jauh dari komentar Suresh, tampaknya ada perbedaan besar dalam praktik. Ada heuristik yang berhasil mengeksploitasi struktur instance SAT praktis dan mendapatkan kinerja yang sangat baik (saya merujuk pada pemecah pembelajaran klausa yang didorong konflik di sini). Heuristik yang sama tidak menghasilkan peningkatan kinerja yang serupa pada pemecah QBF.

Perbedaan antara bukti dan verifikasi juga muncul. Beberapa pemecah SAT (seperti MiniSAT 1.14 dan sejumlah lainnya) menghasilkan bukti. Memproduksi bukti dalam pemecah QBF saat ini adalah non-sepele. (Pernyataan berikutnya adalah dari kabar angin). Ada banyak contoh dalam kompetisi QBF di mana solver ternyata menghasilkan hasil yang berbeda. Dengan tidak adanya pemecah bukti, kita tidak tahu hasil mana yang benar.

Jika Anda melihat kinerja praktis pada SAT dan catur, maka ada perbedaan - Masalah NP-lengkap lebih mudah ditangani daripada masalah PSPACE-complete. Pemecah SAT saat ini dapat menangani lebih dari ribuan variabel, tetapi mesin catur terbaik, dalam jumlah waktu yang sama, hanya dapat menghitung di bawah 20 gerakan.

Saya kira ini karena struktur masalah. Ya, jika Anda hanya menyebutkan solusi, pemecahan SAT sangat lambat. Tetapi karena tidak memiliki pergantian kuantifikasi, orang menemukan struktur dalam rumus dan karenanya menghindari banyak enumerasi. Saya pikir Ryan Williams mengabaikan hal ini.

Dengan pergantian kuantifikasi, ya ada metode pemangkasan yang cerdas, tetapi strukturnya tidak sekaya formula CNF.

Biarkan saya memprediksi masa depan. Pemecahan SAT akan mencapai P dengan memeriksa rumus dan pada dasarnya menghindari pencarian, sementara catur akan membuatnya ke P dengan memanfaatkan pencarian di pohon permainan.