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

8

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

Bk: ={φ|φadalah wff dari ZF dan memiliki bukti panjangk|φ|k}

Sekarang untuk semua k, bahasa Bk dalam NP karena bukti yang valid untuk φ panjangnya k|φ|kdapat menjadi saksi NP yang diverifikasi oleh pemeriksa bukti otomatis dalam waktu polinomial. Selanjutnya untuk yang cukup besark, Bk NP-complete karena SAT menguranginya: yaitu, misalnya ϕ SAT membuat wff yang sesuai dari ZF φmenggunakan quantifier eksistensial. Kemudian penugasan kebenaran yang memuaskanϕ dapat dibuat menjadi bukti formal φ panjang polinomial dalam |φ| sejak penugasan kebenaran ϕ linear dalam |ϕ|.

Sekarang, jika ZF tidak konsisten, ini berarti ada pernyataan formal σ sedemikian rupa sehingga keduanya σ dan ¬σpunya bukti di ZF. Seperti diketahui, pernyataan lainnyaτ kemudian dapat diturunkan dari konjungsi kontradiktif σ¬σ (yaitu dengan mengikuti jalan:

σ¬σbothσand¬σare true¬τσis true (since regardless ofτthe implication is valid sinceσis true)¬στ(by contraposition and double negation)τ is true (by modus ponens with¬σ)

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

Membiarkan B:=Bk untuk yang cukup besar k a sebagaimana dimaksud di atas untuk memungkinkan Bmenjadi NP-complete. Maka jika ZF tidak konsisten, hanya ada banyakφ seperti yang φB karena tunjangan panjang polinomial bukti tingkat tinggi Bcukup untuk menutupi bukti pendek terjamin dari panjang yang cukup. Ini menyiratkan bahwaBdapat 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.

Ari
sumber

Jawaban:

6

Tampaknya ada kekurangan yang disinggung oleh Arno dalam jawabannya. Sedangkan pengurangannyaSATBtampaknya 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.φ yang tidak memiliki bukti yang relatif singkat.

Jadi, jika kita asumsikan bahwa ZF konsisten dan ZFPNP maka meskipun kita dapat menyimpulkan secara metamatis itu BP (karena menjadi NP-lengkap, B tidak bisa masuk P karena kita mengasumsikan PNP) kami tidak akan memiliki pengurangan resmi ZFBP (karena ini tergantung pada Bmenjadi 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 dariZFPNP.

Ari
sumber
Kerja bagus! ini tampaknya menjadi masalah.
Ariel
4

Masalahnya adalah dalam pernyataan Anda bahwa cukup besar k, bahasa Bkadalah 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 Bkapakah NP-selesai? Ini hanya asumsi yang diperlukan untuk bahasaBkmenjadi 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