Mengapa teorema ketidaklengkapan kedua Godel tidak mengesampingkan bukti P! = NP yang dapat diformalkan?

Saya yakin pasti ada yang salah dengan alasan berikut karena jika tidak banyak penelitian P vs NP akan dikurangi tetapi saya tidak dapat menentukan kesalahan saya:

Untuk bilangan bulat tetap $k>0$ menetapkan

B_{k} : = {⟨ φ ⟩ | φ adalah wff dari ZF dan memiliki bukti panjang \leq k {| φ |}^{k}}

$B_k := \{ \langle \varphi \rangle | \; \varphi \; \text{is a wff of ZF and has a proof of length} \; \leq k{|\varphi|}^k \; \}$

Sekarang untuk semua $k$ , bahasa $B_k$ dalam NP karena bukti yang valid untuk $\varphi$ panjangnya $\leq k{|\varphi|}^k$ dapat menjadi saksi NP yang diverifikasi oleh pemeriksa bukti otomatis dalam waktu polinomial. Selanjutnya untuk yang cukup besar $k$ , $B_k$ NP-complete karena SAT menguranginya: yaitu, misalnya $\phi$ SAT membuat wff yang sesuai dari ZF $\varphi$ menggunakan quantifier eksistensial. Kemudian penugasan kebenaran yang memuaskan $\phi$ dapat dibuat menjadi bukti formal $\varphi$ panjang polinomial dalam $|\varphi|$ sejak penugasan kebenaran $\phi$ linear dalam $|\phi|$ .

Sekarang, jika ZF tidak konsisten, ini berarti ada pernyataan formal $\sigma$ sedemikian rupa sehingga keduanya $\sigma$ dan $\neg \sigma$ punya bukti di ZF. Seperti diketahui, pernyataan lainnya $\tau$ kemudian dapat diturunkan dari konjungsi kontradiktif $\langle \sigma \wedge \neg \sigma \rangle$ (yaitu dengan mengikuti jalan:

⟨ σ \land \neg σ ⟩ ⟹ both σ and \neg σ are true ⟹ ⟨ \neg τ \to σ ⟩ is true (since regardless of τ the implication is valid since σ is true) ⟹ ⟨ \neg σ \to τ ⟩ (by contraposition and double negation) ⟹ τ is true (by modus ponens with \neg σ)

$\langle \sigma \wedge \neg \sigma \rangle \implies \text{both} \; \sigma \; \text{and} \; \neg \sigma \; \text{are true} \implies \langle \neg \tau \rightarrow \sigma \rangle \; \text{is true (since regardless of} \; \tau \; \text{the implication is valid since} \; \sigma \; \text{is true)} \implies \langle \neg \sigma \rightarrow \tau \rangle \; \text{(by contraposition and double negation)} \implies \tau \; \text{ is true (by modus ponens with} \; \neg \sigma \, )$

). Jadi jika ZF tidak konsisten, maka setiap pernyataan $\varphi$ memiliki polinomial bukti (menurut saya bahkan hanya linier) di $|\varphi|$ .

Membiarkan $B:=B_k$ untuk yang cukup besar $k$ a sebagaimana dimaksud di atas untuk memungkinkan $B$ menjadi NP-complete. Maka jika ZF tidak konsisten, hanya ada banyak $\varphi$ seperti yang $\langle \varphi \rangle \notin B$ karena tunjangan panjang polinomial bukti tingkat tinggi $B$ cukup untuk menutupi bukti pendek terjamin dari panjang yang cukup. Ini menyiratkan bahwa $B$ dapat ditentukan dalam waktu polinomial yang dengan NP-kelengkapannya menyiratkan bahwa P = NP. Jika kita menguraikan kembali rantai penalaran ini dalam hal kontrasepsi, jika P! = NP maka ZF tidak tidak konsisten (itu konsisten).

Karena itu Jika kami memiliki bukti formal P! = NP maka kami memiliki bukti formal tentang konsistensi ZF. Tetapi dengan teorema Incompleteness Kedua Godel, ini menyiratkan bahwa ZF tidak konsisten yang pada gilirannya mendapatkan P = NP seperti yang diuraikan di atas (serta teorema dari setiap teorema yang dinegasikan).

Ini bukan bukti bahwa P vs. NP tidak tergantung pada ZF. Bisa jadi ZF konsisten dan P = NP atau P! = NP dapat dibuktikan melalui teknik yang tidak dapat diformalkan dalam ZF. Namun, itu menghadirkan penghalang tangguh lain untuk menyelesaikan P vs NP.

complexity-theory np-complete logic p-vs-np Ari
sumber

Jawaban:

Tampaknya ada kekurangan yang disinggung oleh Arno dalam jawabannya. Sedangkan pengurangannya $SAT \leq B$ tampaknya cukup berbahaya (dan memang merupakan latihan buku teks seperti yang ditunjukkan oleh Ariel dalam komentarnya) itu secara implisit mengasumsikan konsistensi ZF. Kalau tidak, jika ZF tidak konsisten, karena setiap pernyataan ZF kemudian akan memiliki bukti, instance-instance SAT yang tidak memuaskan tidak perlu dipetakan ke wffs. $\varphi$ yang tidak memiliki bukti yang relatif singkat.

Jadi, jika kita asumsikan bahwa ZF konsisten dan $ZF \vdash P \neq NP$ maka meskipun kita dapat menyimpulkan secara metamatis itu $B \notin P$ (karena menjadi NP-lengkap, $B$ tidak bisa masuk $P$ karena kita mengasumsikan $P \neq NP$ ) kami tidak akan memiliki pengurangan resmi $ZF \vdash B \notin P$ (karena ini tergantung pada $B$ menjadi set NP-complete yang mapan, jadi jika kita ingin menggunakan reduksi di atas, kita harus mengasumsikan bahwa ZF konsisten, yang tidak dapat secara formal dinyatakan oleh Teorema Ketidakcocokan Kedua Godel). Jadi argumen ini tidak dapat menyarankan implikasi yang diperlukan dari $ZF \vdash P \neq NP$ .

Ari
sumber

Kerja bagus! ini tampaknya menjadi masalah.

Ariel

Masalahnya adalah dalam pernyataan Anda bahwa cukup besar $k$ , bahasa $B_k$ adalah NP-lengkap. Dalam pengurangan yang Anda usulkan, Anda hanya berpendapat bahwa instance-SAT yang memuaskan adalah formula-ZF dengan bukti "pendek". Namun, Anda juga perlu berargumen bahwa kapan pun formula ZF yang dihasilkan memiliki bukti pendek, maka instance-SAT yang asli adalah memuaskan. Ini tentu saja bermuara pada mengatakan bahwa jika ZF membuktikan bahwa instance-SAT memuaskan, maka itu benar-benar - tetapi di sini kita menggunakan kesehatan ZF.

Arno
sumber

Anda benar karena saya secara implisit mengasumsikan kesehatan ZF dan kebenaran pemeriksa bukti, tetapi bagaimana hal ini memengaruhi bukti bahwa

B_{k}

$B_k$ apakah NP-selesai? Ini hanya asumsi yang diperlukan untuk bahasa

B_{k}

$B_k$ menjadi menarik. Di bawah reduksi saya, hanya contoh SAT yang memuaskan yang akan memiliki bukti berapa pun panjangnya karena yang tidak memuaskan sesuai dengan pernyataan ZF yang salah.

Ari

@Ari Sat-instance SAT yang tidak memuaskan berhubungan dengan pernyataan ZF yang salah dalam meta-teori Anda. Jadi agar pengurangan berfungsi, Anda perlu agar pernyataan ZF palsu tidak memiliki bukti ZF.

Arno

Kesetaraannya jelas, jika formula memiliki bukti maka instance SAT memuaskan (ZF adalah suara, saya tidak melihat mengapa ini harus menjadi hambatan di sini). Lihat pertanyaan ini untuk membuktikan kelengkapan NP-nya.

Ariel

@Riel Jawaban dalam pertanyaan itu tidak tepat pada apa asumsi itu. Ini perlu mengasumsikan bahwa ZF baik. Hanya pengingat: "Suara" berarti bahwa jika suatu pernyataan memiliki bukti, maka itu sebenarnya benar. Jika ZF tidak konsisten, maka itu membuktikan segalanya, dan karenanya tidak bisa terdengar. Secara khusus, kita melihat bahwa "ZF adalah suara" bukan teorema ZF. Jika meta-teori kami membuktikan "ZF baik", maka itu juga membuktikan "ZF konsisten", dan tidak ada masalah. Jika tidak membuktikannya, maka kami tidak memiliki bukti kelengkapan NP, dan tidak ada masalah juga.

Arno

Kebenaran pengurangan memang bergantung pada konsistensi ZF, namun tidak ada hubungannya dengan kesehatan. Ingatlah bahwa kesehatan didefinisikan relatif terhadap beberapa semantik, dan ZF adalah suara dalam arti bahwa pernyataan yang dapat dibuktikan benar di semua model, jika ZF tidak konsisten bahwa suara itu kosong karena tidak memiliki model.

Ariel