Apakah setiap masalah NP-hard dapat dihitung?

Apakah diperlukan bahwa masalah NP-hard harus dapat dihitung?

Saya kira tidak, tapi saya tidak yakin.

Tidak, masalah -keras tidak harus dapat dihitung. Definisi ini cukup lengkap: masalah adalah jika masalah yang memiliki solusi poli-waktu menyiratkan setiap masalah dalam memiliki solusi poli-waktu (yaitu, pengurangan untuk ada untuk setiap masalah dalam NP .).$NP$$L$$NP$$NP$$L$$NP$

Masalah yang tidak dapat diperhitungkan kemudian sangat sulit: misalkan kita dapat menyelesaikannya dalam waktu polinomial. Lalu kami menggunakan bukti bahwa tidak dapat diperhitungkan untuk memperoleh bahwa itu dapat dihitung dan tidak dapat dihitung, sebuah kontradiksi. Dari kepalsuan ini, kita dapat memperoleh apa pun, yaitu bahwa ada algoritma waktu polinomial untuk masalah NP apa pun yang $NP$kita lihat.

Sebagai contoh, mempertimbangkan penghentian masalah $H$ . Kami dapat mengurangi bahasa NP A ke H sebagai berikut, dengan asumsi kami memiliki pemeriksa poli waktu f (s, c) yang memeriksa apakah c adalah sertifikat untuk s \ dalam A :$NP$$A$$H$$f(s,c)$$c$$s\in A$

• Masukan yang diberikan $s$
• Konstruk (tetapi tidak menjalankan) Turing Machine $M$ yang mengambil input $x$ mencoba setiap sertifikat $c$ dan perhentian jika $c$ adalah sertifikat memverifikasi bahwa $s\in A$ .
• Kembalikan $H(M,x)$ (yaitu, kembalikan true jika $M$ berhenti pada input $x$ )

Dengan demikian, dengan satu panggilan ke algoritma poly-time yang menyelesaikan Masalah Putus, kita dapat menyelesaikan masalah apa pun dalam waktu polinomial.$NP$

Pengurangan seperti itu tidak berguna, karena yang dilakukannya hanyalah mengatakan jika "jika salah maka sesuatu". Kita sudah tahu bahwa tidak ada algoritma polytime untuk masalah yang tidak dapat dihitung.

Tampaknya ada beberapa kebingungan dalam komunitas ini mengenai pertanyaan ini. Saya akan memberikan jawaban terinci dengan harapan membersihkan air dan menerangi hubungan antara kemampuan komputasi dan kekerasan NP.

Pertama, saya percaya bahwa menjadi jelas dan eksplisit tentang berbagai definisi yang terlibat akan menyelesaikan banyak kebingungan.

Sebuah String adalah urutan terbatas karakter dari beberapa abjad yang terbatas tetap.

Masalah keputusan adalah serangkaian string. (Set ini biasanya tidak terbatas.) Pikirkan masalah keputusan sebagai pengujian string untuk beberapa properti: string dengan properti di set, dan string tanpa properti tidak.

Asumsikan kita memiliki dua masalah keputusan, dan . Say adalah polinomial-waktu yang dapat direduksi menjadi jika ada beberapa polinomial dan algoritma beberapa algoritma sehingga, untuk semua string ,B A B p ( x ) M $A$$B$$A$$B$$p(x)$$M$$s$

• Jika Anda memberikan dengan input , berhenti dalam kurang dari langkah (di mana adalah panjang string ) dan menghasilkan string .s M p ( | s | ) | s | s M ( s $M$$s$$M$$p(|s|)$$|s|$$s$$M(s)$
• A M ( s ) $s$ dalam jika dan hanya jika di .$A$$M(s)$$B$

Masalah keputusan adalah NP-keras jika, untuk setiap NP masalah keputusan , adalah polinomial-waktu direduksi menjadi .A A $B$$A$$A$$B$

Masalah keputusan dihitung jika ada algoritma , bahwa, untuk semua string ,$M$$s$

• Jika Anda memberi input , menghentikan dan mengeluarkan "ya" atau "tidak".s $M$$s$$M$
• Outputnya "ya" jika ada di dan "tidak" sebaliknya.$s$$A$

Dengan definisi di atas, kami dapat segera mengklarifikasi apa yang menurut saya mungkin menjadi akar kebingungan dalam pertanyaan Anda: tidak ada dalam definisi masalah keputusan, pengurangan, atau kekerasan NP yang mengharuskan masalah keputusan dapat dihitung. Definisi tersebut masuk akal untuk berpikir tentang masalah keputusan sebagai set string yang sewenang-wenang, dan set ini memang bisa sangat jahat.

Itu meninggalkan dua pertanyaan di atas meja:

1. Definisi tetap membuka kemungkinan bahwa fungsi yang tidak dapat dikomputasi mungkin NP-hard. Apakah sebenarnya ada fungsi NP-hard yang tidak dapat dikomputasi?
2. Ada intuisi yang mengatakan bahwa suatu masalah adalah NP-hard adalah mengatakan bahwa itu sulit untuk dipecahkan. Mengatakan itu tidak dapat dikomputasi sama seperti mengatakan itu "sangat sulit" untuk dipecahkan. Jadi, apakah semua masalah yang tidak dapat dihitung NP-hard?

Pertanyaan 1 lebih mudah dijawab. Ada dua cara yang sangat penting untuk menemukan masalah keputusan yang tidak dapat dihitung yang merupakan NP-hard. Yang pertama adalah masalah terputus-putus: masalah terputus-putus, , memiliki properti bahwa setiap dihitung masalah keputusan polinomial-waktu direduksi menjadi . Karena masalah NP dapat dihitung, setiap masalah NP adalah waktu polinomial yang dapat direduksi menjadi , sehingga adalah NP-hard.H H $H$$H$$H$$H$

Cara penting lainnya untuk membangun masalah NP-hard yang tidak dapat dikomputasi adalah dengan mengamati bahwa kita dapat menggabungkan masalah NP-hard yang diketahui dengan masalah yang tidak dapat dihitung yang diketahui. Biarkan menjadi NP-hard dan menjadi tidak dapat dihitung. Bentuk masalah keputusan sebagai berikut: berisi string-string dari bentuk "0, diikuti oleh string dalam " dan orang-orang dari bentuk "1, diikuti oleh string dalam ". adalah NP-hard karena kita dapat mengubah reduksi apa pun (dari masalah apa pun) menjadi menjadi reduksi menjadi : cukup algoritme untuk mengeluarkan "0" tambahan di bagian depan string keluarannya. B A ⊕ B A ⊕ B A B A ⊕ B A A ⊕ B A ⊕ B A ⊕ B $A$$B$$A \oplus B$$A \oplus B$$A$$B$$A \oplus B$$A$$A \oplus B$$A \oplus B$tidak dapat , karena komputasi membutuhkan memutuskan string mana yang dimulai dengan "1" yang ada dalam set; ini tidak mungkin, karena tidak dapat dihitung.$A \oplus B$$B$

Pertanyaan 2 adalah sangat penipu, tetapi sebenarnya ada masalah keputusan yang tidak dapat dihitung yang tidak NP-keras (dengan asumsi P NP). Jawaban baik Yuval membuat masalah keputusan seperti itu secara eksplisit. (Untuk setiap ahli teori komputasi di dalam ruangan, "Cohen " apa pun akan melakukan trik, juga.) Saya akan menjelaskan mengapa intuisi bahwa "masalah NP-hard sulit, masalah non-computable adalah lebih sulit "salah.Π 0 $\neq$$\Pi^0_1$

NP-hardness dan non-computability keduanya mengatakan bahwa masalah adalah "keras" dalam arti yang sangat umum, tetapi mereka sangat berbeda dan tidak boleh disatukan sebagai fenomena yang sama. Secara khusus, kekerasan NP adalah properti "positif": masalah NP-hard sulit dalam arti bahwa, dengan akses ke lembar contekan untuk A , Anda dapat memecahkan masalah kelas hard$A$$A$ . Di sisi lain, non-komputabilitas adalah properti "negatif": masalah yang tidak dapat dihitung sulit dalam arti bahwa Anda tidak dapat menyelesaikan A dengan kelas sumber daya tertentu$A$$A$ .

( "Memaksa," by the way, adalah teknik yang digunakan untuk menghasilkan "Cohen generik" yang saya sebutkan. Untuk menjadi sangat sangat jelas, memaksa adalah cara umum untuk menghasilkan hal-hal yang "generik" dalam bahwa mereka memiliki tidak ada sifat positif dan setiap sifat negatif. Itu sebabnya memaksa dapat langsung menghasilkan masalah yang tidak dapat dihitung atau NP-keras.)$\Pi^0_1$

Nggak. NP-Hard berarti sama sulitnya, atau lebih sulit, daripada masalah NP yang paling sulit. Secara intuitif, tidak dapat dihitung akan membuatnya jauh lebih sulit daripada NP.

Wikipedia:

Ada masalah keputusan yang NP-keras tetapi tidak NP-lengkap, misalnya masalah terputus-putus.

Semua orang tahu itu tidak bisa dihitung

Untuk kelengkapan, mari kita buktikan teorema berikut:

Ada bahasa yang tidak dapat dihitung yang bukan NP-hard jika dan hanya jika P NP.$\neq$

Jika P = NP maka bahasa non-trivial (yang berbeda dari ) adalah NP-hard (latihan), dan khususnya bahasa yang tidak dapat dihitung adalah NP-hard.$\emptyset,\{0,1\}^*$

Sekarang anggaplah P NP. Biarkan T i menjadi enumerasi semua mesin Turing. Kami akan menyusun bahasa L yang diperlukan secara bertahap. Pada setiap tahap kami akan menjaga { 0 , 1 , ? } pewarnaan { 0 , 1 } ∗ yang juga kami tunjukkan dengan L ; di sini 0 berarti bahwa kita telah memutuskan bahwa string tidak dalam L , 1 berarti kita telah memutuskan bahwa string ada di L , dan $\neq$$T_i$$L$$\{0,1,?\}$$\{0,1\}^*$$L$$0$$L$$1$$L$$?$berarti kita belum memutuskan. Semua kecuali banyak string akan diwarnai .$?$

Pada langkah , kita menganggap T i sebagai mesin yang menerima inputnya, menolaknya, atau tidak pernah berhenti. Jika T i tidak selalu menghentikan maka kita tidak melakukan apa-apa. Jika T saya selalu berhenti maka kita menemukan string x sedemikian rupa sehingga L ( x ) = ? , dan set L ( x ) : = 0 jika T i ( x ) menerima dan L ( x ) : = 1 jika $2i$$T_i$$T_i$$T_i$$x$$L(x) = ?$$L(x) := 0$$T_i(x)$$L(x) := 1$ menolak.$T_i(x)$

Pada langkah , kita menganggap T i sebagai mesin yang menghitung fungsi parsial (mungkin) pada inputnya. Jika T i tidak total, atau jika total tetapi tidak berjalan dalam waktu polinomial, atau jika total tetapi rentangnya terbatas, kami tidak melakukan apa-apa. Jika T i adalah total, berjalan dalam waktu polinomial, dan memiliki rentang tak hingga, maka kita menemukan string x sedemikian rupa sehingga L ( T i ( x ) ) = ? . Jika x ∈ S A T (yaitu, jika $2i+1$$T_i$$T_i$$T_i$$x$$L(T_i(x)) = ?$$x \in \mathrm{SAT}$$x$mengkodekan CNF yang memuaskan) maka kita menetapkan , dan sebaliknya kita menetapkan L ( x ) : = 1 .$L(x) := 0$$L(x) := 1$

Setelah jauh banyak langkah, kita mendapatkan pewarnaan { 0 , 1 } ∗ yang kami selesaikan ke bahasa aktual dengan cara yang sewenang-wenang.$\{0,1,?\}$$\{0,1\}^*$

Yang dihasilkan bahasa tidak dihitung: Langkah 2 i memastikan bahwa T i tidak menghitung itu. Ini juga bukan NP-hard, tapi di sini alasannya sedikit lebih rumit. Misalkan T i adalah pengurangan polytime dari SAT ke L . Jika rentang T i terbatas, maka kita dapat mengubah T i menjadi mesin polytime yang memutuskan SAT, dengan mendaftarkan tabel kebenaran L pada kisaran T i . Ini tidak mungkin dengan asumsi P ≠ NP. Jadi T i memiliki rentang tak terbatas, tetapi kemudian langkah 2 $L$$2i$$T_i$$T_i$$L$$T_i$$T_i$$L$$T_i$$\neq$$T_i$ aturan keluar yang menjadi pengurang SAT ke L .$2i+1$$L$

Sebuah bahasa adalah NP-keras jika untuk setiap L ' ∈ N P kita mendapati bahwa L ' adalah polinomial-waktu direduksi menjadi L . Masalah penerimaan untuk mesin Turing nondeterministic$L$$L' \in \mathrm{NP}$$L'$$L$

tidak dapat ditentukan dan NP-hard. Untuk mempertimbangkan . L ' diputuskan oleh beberapa mesin Turing nondeterministic M ' dengan kompleksitas waktu polinomial. Pengurangan waktu poli f dari L ′ ke A N T M diberikan oleh$L' \in \mathrm{NP}$$L'$$M'$$f$$L'$$A_{\mathsf{NTM}}$

Saya pikir apa yang menyebabkan orang berpikir tidak ada masalah NP-hard yang tidak dapat diperhitungkan adalah bahwa mereka kehilangan titik bahwa kekerasan NP adalah batas bawah pada kekerasan masalah, bukan batas atas pada kekerasan mereka seperti P atau NP.

Bahasa L menjadi NP-hard berarti bahwa itu di atas bahasa di NP dan itu. Sekarang jika Anda memahami hal ini, apa yang dibutuhkan adalah menunjukkan bahwa ada masalah yang lebih sulit dan sewenang-wenang.

Biarkan menjadi bahasa. Pertimbangkan algoritma ditambah dengan kotak hitam yang dapat mereka gunakan untuk memutuskan keanggotaan dalam A . Mari kita menunjukkan mereka dengan C A . Sangat mudah untuk melihat bahwa masalah terputus-putus untuk C A , H a l t C A tidak di C A .$A$$A$$\mathsf{C}^A$$\mathsf{C}^A$$Halt_{\mathsf{C}^A}$$\mathsf{C}^A$

Dalam teori computablity ini disebut melompat dari dan dilambangkan dengan A ' . Jadi A < A ′ dengan ketat. Dan tidak ada yang menghentikan kita untuk mengulangi ini: A < A ′ < A ″ < A ‴ < . . $A$$A'$$A < A'$$A<A'<A''<A'''<...$