Mengapa masalah ini tidak diputuskan dalam NP?

25

Jelas tidak ada masalah yang tidak dapat dipastikan dalam NP. Namun, menurut Wikipedia :

NP adalah himpunan semua masalah keputusan yang contohnya adalah "ya" memiliki [.. bukti yang] dapat diverifikasi dalam waktu polinomial oleh mesin Turing deterministik.

[...]

Suatu masalah dikatakan dalam NP jika dan hanya jika ada verifikasi untuk masalah yang dieksekusi dalam waktu polinomial.

Sekarang pertimbangkan masalah berikut:

Diberikan persamaan Diophantine , apakah ia memiliki solusi integer?

Mengingat solusi, mudah untuk memverifikasi dalam waktu polinomial bahwa itu benar-benar adalah solusi: hanya pasang angka ke dalam persamaan. Dengan demikian, masalahnya ada di NP. Namun, menyelesaikan masalah ini terkenal tidak dapat dipungkiri !

(Demikian pula, tampaknya masalah penghentian harus di NP, karena solusi "ya" dari "program ini berhenti pada langkah ke-N" dapat diverifikasi dalam langkah N.)

Jelas ada yang salah dengan pemahaman saya, tapi apa itu?

BlueRaja - Danny Pflughoeft
sumber
1. Ingatlah bahwa definisi yang Anda kutip adalah untuk masalah keputusan. 2. Mengenai contoh Diophantine Anda, Anda tidak mengklaim bahwa setiap sistem di sana memiliki ikatan polinom pada ukuran solusi, bukan?
Dmitri Chubarov
@ Dmitri: Er, ya saya mengklaim itu. Ukuran solusi persis sama dengan ukuran masalah - jika ada N tidak diketahui, solusinya berisi N bilangan bulat. Dan ini adalah masalah keputusan - solusi integer (diperlukan untuk memverifikasi kasus "ya") akan menjadi sertifikatnya .
BlueRaja - Danny Pflughoeft
19
Pertanyaannya adalah, seberapa besar intgerernya
Artem Kaznatcheev
10
@ BlueRaja-DannyPflughoeft jika Anda memiliki alfabet tak terbatas untuk menyandikan bilangan bulat Anda maka Anda tidak lagi berada dalam pengaturan standar teori kompleksitas. Dengan alfabet terbatas ukuran pengkodean tumbuh dengan nilai integer.
Dmitri Chubarov
Solusi untuk masalah penghentian hanya akan mengembalikan "Ya", tanpa memberikan petunjuk tentang berapa banyak langkah untuk disimulasikan untuk verifikasi.
RemcoGerlich

Jawaban:

10

Definisi ekivalen NP adalah bahwa ia terdiri dari semua masalah yang dapat diurai (bukan hanya dapat diverifikasi) dalam waktu polinomial oleh mesin Turing non-deterministik. NTM diketahui tidak lebih kuat dari TMs dalam arti bahwa serangkaian masalah yang dapat diputuskan oleh NTM identik dengan serangkaian masalah yang dapat diputuskan oleh TMs, jadi jelas dengan definisi ini tidak ada masalah yang tidak dapat diputuskan dalam NP.

Untuk menunjukkan bahwa dua definisi NP adalah setara, mengingat keberadaan verifier deterministik Anda dapat menunjukkan bahwa penentu non-deterministik ada, dan sebaliknya.

Katakanlah Anda memiliki verifikasi polinomial deterministik. Lalu ada juga mesin yang secara non-deterministik menebak sertifikat yang panjangnya dibatasi oleh polinomial yang sesuai dengan ukuran sertifikat yang terikat pada masalah / verifikasi ini dan kemudian menjalankan verifikasi. Karena alfabetnya terbatas, sertifikat untuk setiap input yang diberikan adalah terbatas (dan paling banyak polinomial dalam ukuran input), dan verifier berjalan dalam waktu polinomial, mesin berhenti di semua cabang untuk semua input dan berjalan di (non- deterministik) waktu polinomial. Jadi ada penentu non-deterministik untuk setiap verifier deterministik.

Jika Anda memiliki penentu non-deterministik, maka untuk setiap perhitungan yang menerima Anda dapat menuliskan jalur pilihan yang diambil oleh penentu untuk mencapai keadaan penerimaan. Karena penentu berjalan dalam waktu polinomial, jalur ini paling panjang polinomial. Dan sangat mudah untuk TM deterministik untuk memvalidasi bahwa jalan tersebut adalah jalan yang valid melalui NTM ke menerima keadaan, sehingga jalur tersebut membentuk sertifikat untuk waktu polinomial verifier untuk masalah tersebut. Jadi ada verifikasi deterministik untuk setiap penentu non-deterministik.

Jadi setiap masalah yang tidak dapat diputuskan tidak dapat memiliki verifier yang berfungsi pada sertifikat dengan ukuran polinomial (jika tidak, keberadaan verifier akan menyiratkan adanya penentu).


Ketika Anda mengklaim bahwa ada verifikasi untuk masalah penghentian, sertifikat yang Anda bicarakan adalah beberapa penyandian (TM, I, N), di mana TM berhenti pada input I dalam langkah-langkah N. Ini memang dapat diverifikasi dalam langkah-langkah N, tetapi ukuran sertifikat tidak polinomial dalam ukuran input (TM, I) ke masalah asli (masalah terputus-putus); N dapat menjadi besar secara arbitrer (terlepas dari pengkodean). Jika Anda mencoba mengonversi verifikasi seperti itu menjadi penentu non-deterministik, Anda berakhir dengan mesin yang agak menarik. Anda harus dapat membuktikan bahwa ketika dijalankan pada (TM, I) untuk TM yang tidakberhenti pada input Saya tidak ada jalur non-berhenti melalui mesin, tetapi juga bahwa untuk setiap jalur yang mengarah ke keadaan berhenti selalu ada jalan lagi yang lebih panjang (sesuai dengan perkiraan N yang lebih besar), dan dengan demikian tidak ada batas yang terbatas pada waktu eksekusi. Pada dasarnya ini adalah karena ada ruang tak terbatas yang perlu dieksplorasi oleh tebakan non-deterministik awal. Mengubah NTM seperti itu menjadi TM deterministik mengarah ke salah satu mesin yang tidak memotong atau berhenti pada beberapa input. Bahkan tidak ada NTM yang dapat memutuskan masalah penghentian, dan karenanya tidak ada verifikasi yang bekerja pada sertifikat dengan ukuran terbatas.

Saya tidak begitu akrab dengan persamaan Diophantine, tetapi sepertinya pada dasarnya masalah yang sama berlaku untuk argumen Anda di sana.

Untuk alasan ini saya merasa lebih mudah untuk menjelaskan tentang definisi NTM untuk NP. Ada pengukur untuk masalah yang tidak dapat diputuskan (hanya saja tidak yang bekerja pada sertifikat yang memiliki ukuran polinomial terikat dalam ukuran input ke masalah asli). Faktanya, setiap TM yang mengenali tetapi tidak memutuskan beberapa bahasa dapat dengan mudah dikonversi menjadi pemverifikasi untuk bahasa yang sama.

Jika Anda benar-benar memikirkan tentang verifier, saya kira Anda harus memberikan batasan waktu dalam hal ukuran input masalah asli , bukan dalam hal ukuran sertifikat; Anda dapat secara sembarangan mengembang ukuran sertifikat sehingga verifikasi berjalan dalam batas waktu yang lebih rendah dalam hal ukuran sertifikat.

Ben
sumber
26

Saya pikir Anda salah paham apa artinya menyelesaikan persamaan diophantine, dan teorema keragu-raguan Matiyasevich .

Matiyasevich membuktikan bahwa untuk setiap RE set ada diophentine persamaan f ( n ; x 1 , . . . , X k ) sehingga n S hanya jika ada bilangan bulat koefisien x 1 , .., x k sehingga f ( n ; x 1 , . . . , x k ) = 0Sf(n;x1,...,xk)nSx1xkf(n;x1,...,xk)=0. Secara khusus, masalah penghentian adalah set RE yang khas, dan dengan demikian menyelesaikan masalah di atas tidak dapat diputuskan.

Perhatikan bahwa tidak dibatasi dalam ukuran, dan secara umum dapat sewenang-wenang besar, sehingga tidak ada "polinomial berukuran sertifikat" jelas dalam masalah ini.x1,...xk

Untuk memperluas: bilangan bulat perlu ditulis dalam biner menjadi sertifikat. Karena bilangan bulat ini bisa besar secara arbitrer (berapapun n ), kami memiliki sertifikat yang tidak polinomial dalam log n atau yang lebih penting, tidak dibatasi oleh dan fungsi yang dapat dihitung.x1,...,xknlogn

Namun setiap masalah dalam , memiliki sertifikat yang dibatasi oleh beberapa polinomial p ( N ) (di mana N adalah ukuran input). Jadi N P pertanyaan yang sepele decidable, karena Anda dapat menghitung setiap bit string yang mungkin upto panjangNPp(N)NNP dan jika tidak satupun dari mereka menyatakan input, palsu kembali. Jika ada yang mengembalikan true.p(N)

Artem Kaznatcheev
sumber
Tentu saja saya mengerti apa artinya "menyelesaikan persamaan diophantine" - Anda menemukan angka yang memenuhi persamaan tersebut. Saya tidak melihat mengapa teorema keragu-raguan Matiyasevich atau kumpulan enumerable rekursif perlu dimasukkan ke dalam diskusi. Tapi saya pikir paragraf terakhir bisa menjelaskannya ...
BlueRaja - Danny Pflughoeft
1
Baiklah suntingan baru ini menjelaskannya - itu juga menjelaskan mengapa masalah Penghentian tidak ada dalam NP, karena langkah-langkah yang diperlukan untuk menghentikannya bisa besar secara sewenang-wenang. Terima kasih!
BlueRaja - Danny Pflughoeft
Suntingan yang saya sarankan adalah menghapus dua paragraf pertama. Dua paragraf pertama menjelaskan mengapa masalah ke-10 Hilbert tidak dapat dipastikan, yang sepenuhnya bersinggungan dengan pertanyaan; mereka hanya mengurangi dari sisa jawaban (yang merupakan jawaban yang bagus jika tidak!) .
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft jika paragraf pertama menghina Anda, maka saya dapat menghapusnya (meskipun Anda bertanya "apa yang salah dengan pemahaman saya ?"). Paragraf kedua diperlukan untuk mengatur masalah secara lebih formal karena Anda tidak ada dalam pertanyaan Anda.
Artem Kaznatcheev
3
@ BlueRaja-DannyPflughoeft Yang terbaik adalah jika pertanyaan dan jawaban mandiri. Paragraf kedua saya mengatur masalah dan menjelaskan apa artinya masalah ini tidak dapat diputuskan. Paragraf ketiga saya memberikan jawaban cepat. Paragraf 4 dan 5 saya mengembangkannya secara lebih rinci. Sejauh yang saya tahu, semua paragraf diperlukan.
Artem Kaznatcheev
8

Anda seharusnya menggulir ke bawah ke definisi formal :

LpqM

  • xMp(|x|)(x,y)
  • xLyq(|x|)M(x,y)=1
  • xLyq(|x|)M(x,y)=0 .

Artinya, verifier harus bekerja juga pada non-solusi. Di suatu tempat di sana, masalah yang tidak dapat dipastikan gagal (dalam kasus Anda, batasan panjang kandidat solusi mungkin tidak terpenuhi), seperti yang terlihat jelas oleh (dalam arti komputabilitas) yang lebih jelas. definisi :

NP adalah serangkaian masalah keputusan yang ditentukan oleh mesin Turing non-deterministik yang beroperasi dalam waktu polinomial.

Raphael
sumber
"verifier harus bekerja juga pada non-solusi" - jika Anda mengatakan verifier perlu gagal untuk non-solusi, itu sudah. Jika Anda mengklaim bahwa verifikator harus dapat memverifikasi jawaban "tidak", itu tidak benar - itu adalah co-NP . Dan saya sudah mengetahui definisi kedua, tetapi saya bingung bagaimana bisa setara dengan yang pertama, karena satu definisi tampaknya mengakui masalah dalam pertanyaan, sedangkan yang lain tidak.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: Pengamatan saya adalah: verifier harus dapat menyangkal non-solusi. Jika Anda mengetahui hal ini, harap edit pertanyaan Anda sesuai; itu membuat Anda terlihat sangat tidak bisa mengerti.
Raphael
Sepele jelas bahwa verifier sudah membantah non-solusi: cukup tancapkan angka ke dalam persamaan dan lihat apakah itu berlaku. Saya khawatir saya tidak mengerti apa yang Anda maksud.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: "Definisi" yang Anda kutip tidak menentukan perilaku ini.
Raphael
-1

Saya mencoba memberikan rincian lebih lanjut untuk jawaban saya di atas.

Sebenarnya, pertanyaan ini adalah masalah dilema.

Di satu sisi, Masalah Persamaan Diophantine (DEP) tidak dapat diputuskan menurut teorema Matiyesevich (teorema Matiyesevich menjawab masalah kesepuluh Hilbert, dan masalah Turing's Halting menjawab generalisasi masalah kesepuluh Hilbert, yaitu Entscheidungsproblem); tetapi di sisi lain, tidak ada masalah yang tidak dapat diputuskan dalam NP menurut definisi NP (decidable and verifiable).

Dengan kata lain, DEP tidak dalam NP, atau DEP dalam NP. Keduanya menyangkut definisi NP.

Jika DEP tidak dalam NP, itu berarti masalah dalam NP (NDTM = Mesin Turing NonDeterminstic) dapat di decidable dan diverifikasi, artinya kita menerima P = NP (NDTM).

Jika DEP dalam NP, maka NP (NTM = Non Turing Machine) mengandung decidable dan undecidable, jelas decidable dapat diverifikasi, oleh karena itu masalahnya adalah apakah undecidable dapat diverifikasi? Bahkan, itu adalah masalah P vs NP yang terkenal. Tentu saja, tidak dapat dipastikan tidak dapat diverifikasi, sehingga NP sesuai dengan NTM (Non Turing Machine) dan bukan NDTM (NonDeterminstic Turing Machine).

Pergi pada premis DEP adalah dalam NP (NTM), kami berpikir bahwa NP (NTM) adalah Masalah Nondeterministic (tidak dapat dipastikan), dan definisi saat ini dari NP (NDTM, decidable dan dapat diverifikasi) telah kehilangan nondeterminism ini (tidak dapat ditentukan), jadi kami pikir itu perlu dipertanyakan.

Yu Li
sumber
1
Tidak, ketidakpastian DEP (masalah kesepuluh Hilbert) tidak ditunjukkan sampai tahun 1970, oleh Matiyesevich. Masalah Entscheidungsproblem bukanlah masalah kesepuluh Hilbert; menyangkut validitas formula logika orde pertama. Dan, sekali lagi, masalah P vs NP sama sekali bukan masalah tentang apakah masalah yang tidak dapat dipastikan dapat diverifikasi.
David Richerby
1
Jika Anda ingin memberikan detail lebih lanjut, Anda harus mengedit posting asli Anda.
Tom van der Zanden
@ DavidvidRicherby Perhatikan bahwa jawaban yang diberikan oleh Ben: «set masalah yang dapat diputuskan oleh NTM identik dengan set masalah yang dapat diputuskan oleh TM». Hanya dalam pengertian ini, saya berpikir bahwa definisi NP membingungkan P dengan NP, dan itu mengarah ke P = NP (NDTM). Jika definisi ini perlu dipertanyakan, maka kesimpulan lain yang disimpulkan dari definisi ini, seperti kesetaraan verifier deterministik dan penentu non-deterministik, juga perlu dipertanyakan.
Yu Li
@YuLi "itu mengarah ke P = NP (NDTM)." Saya tidak tahu apa yang Anda maksud dengan itu. Juga, saya tidak melihat relevansi menunjukkan bahwa TM dan NTM memutuskan bahasa yang sama. Jika mereka tidak memutuskan bahasa yang sama, NTM akan menjadi model perhitungan yang sama sekali tidak masuk akal dan sulit untuk membayangkan bahwa kita peduli apa yang dapat mereka hitung dalam waktu polinomial. Dalam teori kompleksitas, kami mengambil pandangan yang lebih halus dan bertanya tentang sumber daya komputasi yang diperlukan dan definisi NP tidak membingungkan sama sekali.
David Richerby
@DavidRicherby Terima kasih, saya telah memodifikasi jawaban saya sesuai dengan komentar Anda untuk mengklarifikasi hubungan Entscheidungsproblem dan masalah kesepuluh Hilbert. Mengenai pertanyaan tentang definisi NP saat ini, sulit untuk dibahas dalam beberapa kata. Tujuan dari jawaban saya adalah hanya untuk membangkitkan beberapa refleksi tentang topik dasar ini, ...
Yu Li
-2

Kami berpikir bahwa dilema yang Anda ajukan tentang persamaan Diophantine sangat signifikan, karena mengungkapkan sesuatu yang tidak normal dalam definisi NP saat ini: - Masalah dikatakan dalam NP jika dan hanya jika ada verifikasi untuk masalah yang dieksekusi dalam polinomial waktu.

Mengenai definisi NP, dapat ditelusuri ke 60-an, di mana sejumlah besar masalah yang berlaku dan signifikan ditemukan dimana tidak ada algoritma polinom dapat ditemukan untuk menyelesaikannya, untuk mengenali masalah ini dari masalah yang dapat dipecahkan dalam waktu Polinomial. (P), konsep NP dikeluarkan.

Namun, definisi NP saat ini didefinisikan sebagai dapat diverifikasi dalam waktu polinomial membingungkan NP dengan P, karena masalah dalam P juga dapat diverifikasi dalam waktu polinomial. Dengan kata lain, definisi tersebut mengarah pada hilangnya esensi NP, «nondeterminisme». Akibatnya, ini menyebabkan ambiguitas serius dalam memahami NP, misalnya, dilema Anda: secara alami masalah persamaan Diophantine tidak dapat diputuskan; tetapi dengan definisi NP, itu dapat ditentukan, ...

Menurut pendapat kami, kesulitan dalam memecahkan «P versus NP» pertama-tama terletak pada tingkat kognisi, jadi jika kita berharap untuk mendapatkan wawasan tentang «P versus NP», pertama-tama kita perlu bertanya: Apa itu NP?

Yu Li
sumber
4
Ini tampaknya menjadi pendapat tentang definisi NP , bukan jawaban untuk pertanyaan. Definisi NP baik-baik saja. Itu tidak membingungkan P dengan NP ; melainkan, ia mengakui bahwa P adalah subset dari NP . Bagi saya, akan sangat tidak wajar jika P bukan bagian dari NP . NP adalah kelas masalah yang dapat diselesaikan dalam batas sumber daya tertentu. Itu harus mencakup sejumlah masalah mudah ( P ) yang dapat diselesaikan tanpa mendekati batas sumber daya yang tersedia.
David Richerby
@DavidRicherby P dan NP memiliki properti umum «sertifikat dapat diverifikasi dalam waktu polinomial», tetapi properti ini bukan inti dari NP. Jika properti ini digunakan untuk mendefinisikan NP, maka P adalah subset dari NP, dan NP memiliki P sebagai subsetnya (decidable) dan itu sendiri (undecidable). Karena itu, orang akan bertanya-tanya apakah NP dapat dipilih atau tidak diputuskan? Sama seperti dilema di atas: apakah persamaan Diophantine tidak dapat diputuskan atau tidak dapat ditentukan? Jadi jawaban saya adalah menyarankan untuk menyelidiki dilema ini dari sudut pandang definisi NP: dapat diverifikasi, tidak dapat dipastikan tidak dapat diverifikasi!
Yu Li
Masalah dalam NP dapat ditentukan menurut definisi: NP adalah kelas masalah yang diputuskan oleh mesin Turing nondeterministic. Sangat mudah untuk membuktikan bahwa ini adalah set masalah yang sama persis yang memiliki sertifikat panjang polinomial yang dapat diverifikasi dalam waktu polinomial. Jika Anda khawatir bahwa masalah dalam NP mungkin tidak dapat diputuskan, maka Anda telah salah mengerti sesuatu.
David Richerby
Ya, saya khawatir masalah di NP mungkin tidak dapat diputuskan. Anda berbicara tentang kesetaraan dua definisi NP: NP adalah kelas masalah yang diputuskan oleh mesin Turing nondeterministic; NP adalah kelas masalah yang memiliki sertifikat panjang polinom yang diverifikasi dalam waktu polinomial. Saya meragukan kesetaraan ini, karena yang satu adalah tentang keberadaan algoritma untuk memecahkan masalah dan yang lainnya tentang keberadaan solusi untuk suatu masalah. Dilema tentang Persamaan Diophantine mungkin secara langsung terkait dengan kesetaraan ini (lihat detail argumen saya: arxiv.org/abs/1501.01906 ).
Yu Li
2
@ YuLi Kesetaraan dari dua definisi NP begitu mudah bahwa itu diajarkan di kelas teori kompleksitas sarjana. Saya sarankan tidak mengunggah ke ArXiv jika Anda tidak memahami dasar-dasar bidang ini.
David Richerby