Jika P = NP, bisakah kita mendapatkan bukti dugaan Goldbach dll?

Ini adalah pertanyaan naif, dari keahlian saya; permintaan maaf sebelumnya.

Dugaan Goldbach dan banyak pertanyaan lain yang tidak terpecahkan dalam matematika dapat ditulis sebagai rumus pendek dalam predikat kalkulus. Misalnya, makalah Cook "Dapatkah Komputer Secara Rutin Menemukan Bukti Matematika?" merumuskan dugaan itu sebagai

\forall n [(n > 2 \land 2 | n) \supset \exists r \exists s (P (r) \land P (s) \land n = r + s)]

$\forall n [( n > 2 \wedge 2 | n) \supset \exists r \exists s (P(r) \wedge P(s) \wedge n = r + s) ]$

Jika kita membatasi perhatian pada bukti polinomial yang panjang, maka teorema dengan bukti tersebut ada dalam NP. Jadi jika P = NP, kita dapat menentukan apakah dugaan Goldbach benar dalam waktu polinomial.

Pertanyaan saya adalah: Apakah kita juga dapat menunjukkan bukti dalam waktu polinomial?

Edit . Sesuai komentar Peter Shor dan Kaveh, saya harus memenuhi syarat klaim saya bahwa kita dapat menentukan apakah dugaan Goldbach benar jika memang salah satu teorema dengan bukti singkat. Yang mana tentu saja kita tidak tahu!

cc.complexity-theory proof-complexity automated-theorem-proving proof-search Joseph O'Rourke
sumber

Pertama, untuk menunjukkan bukti dugaan Goldbach yang singkat (<1000 halaman?), Harus ada bukti singkat. P = NP tidak ada hubungannya dengan itu.

Peter Shor 8-10

@ Suresh, @Kaveh: Sepertinya kamu salah paham. Di sini kita memiliki contoh konkret masalah pencarian NP. Kuantitas yang relevan di sini adalah keberadaan bukti (dalam sistem formal yang sesuai) dari teorema.

Kristoffer Arnsfelt Hansen

Komentar lain adalah bahwa kita benar-benar dapat menuliskan algoritma, bahwa jika P = NP akan menemukan bukti untuk pernyataan yang diberikan jika ada dalam polinomial waktu dalam panjang pernyataan dan panjang bukti terpendek. (Polinomial ini adalah ikatan yang berlaku untuk semua teorema), namun akan menjadi algoritma "astronomi".

Kristoffer Arnsfelt Hansen

@ Jo: Tidak, saya benar-benar dapat menuliskan algoritme sekarang! (Bahkan tidak tahu jika P = NP). Idenya adalah apa yang dikenal sebagai pencarian Universal Levin.

Kristoffer Arnsfelt Hansen

@Kristoffer: Keren! Tidak tahu tentang LS. Saya melihat bahwa Marcus Hutter memiliki semacam peningkatan pada LS: "Algoritma Tercepat dan Terpendek untuk Semua Masalah yang Didefinisikan dengan Baik." Jurnal Internasional Yayasan Ilmu Komputer, 13 (3): 431-443, 2002.

Joseph O'Rourke

Jawaban:

Memang!

Jika P = NP, tidak hanya kita dapat memutuskan apakah ada bukti panjang n untuk dugaan Goldbach (atau pernyataan matematika lainnya), tetapi kita juga dapat menemukannya secara efisien!

Mengapa? Karena kita dapat bertanya: apakah ada bukti yang dikondisikan pada bit pertama ..., lalu, apakah ada bukti yang dikondisikan pada dua bit pertama adalah ...., dan seterusnya ...

Dan bagaimana kamu tahu? Anda hanya akan mencoba semua kemungkinan, dalam urutan yang meningkat. Ketika kami membuat langkah dalam kemungkinan ke-10, kami juga mencoba langkah di setiap kemungkinan 1 .. (i-1).

Dana Moshkovitz
sumber

Bukankah ini algoritma pencarian universal Levin?

Mohammad Al-Turkistany

@turkistany: ya, benar!

Dana Moshkovitz

Dana telah menjawab pertanyaan itu. Tetapi di sini ada beberapa komentar di sisi praktis.

$P=NP$ $P=NP$ $P=coNP$

$NP$ $l$ $P=NP$ $l$

$P=NP$ $l$ $l$ $P=NP$ $P$ $DTime(n^2)$ ), maka seseorang dapat mengambil algoritma ini dan menjalankannya untuk memeriksa bukti panjang yang layak tetapi sangat besar yang akan menjadi lebih besar dari bukti apa pun yang dapat ditemukan oleh manusia, dan jika algoritma tidak menemukan jawaban, maka Kalimat praktis tidak mungkin dibuktikan. Trik yang disebutkan Dana juga akan berhasil di sini untuk menemukan buktinya.

Untuk cara praktis:

$P=NP$ $DTime(10000n^{10000})$
itu akan menemukan bukti hanya jika ada satu (yaitu kalimat itu bukan kalimat yang tidak dapat diputuskan dalam ZFC), apalagi bukti harus singkat.
$P\neq NP$ $NP=DTime(n^{\log^* n})$

Kaveh
sumber

(n^{10})

$(n^{10})$