Tentang provabilitas P versus NP

Pertama-tama, pemahaman saya tentang teorema ketidaklengkapan Gödel (dan logika formal pada umumnya) sangat naif, juga pengetahuan saya tentang ilmu komputer teoretis (artinya hanya satu mata kuliah yang diambil saat saya masih sarjana), jadi pertanyaan ini mungkin saja sangat naif.

Sejauh yang saya bisa temukan, provabilitas P versus NP adalah masalah terbuka.

Sekarang:

Teorema ketidaklengkapan Gödel yang pertama menyatakan bahwa mungkin ada pernyataan yang benar tetapi tidak dapat dibuktikan atau tidak dapat disangkal.
Jika solusi polinom ditemukan untuk masalah NP-lengkap, itu membuktikan bahwa P = NP.

Jadi, anggaplah bahwa P = NP tidak dapat dibuktikan:
Ini berarti bahwa tidak ada contoh solusi polinomial untuk masalah NP-complete dapat ditemukan (jika tidak, ini akan menjadi bukti).
Tetapi jika tidak ada contoh solusi polinomial untuk masalah NP-complete dapat ditemukan, ini berarti bahwa P = NP adalah salah (membuktikannya, berarti pernyataan itu dapat dibuktikan), yang mengarah pada kontradiksi, oleh karena itu P = NP harus dapat dibuktikan .

Ini kedengarannya sebagai bukti dari provabilitas P = NP bagi saya, tapi saya pikir itu sangat mungkin karena kurangnya pemahaman saya tentang topik logika yang terlibat. Adakah yang bisa membantu saya memahami apa yang salah dengan ini?

np-hardness proofs p-vs-np Alvaro
sumber

Lihat makalah Scott Aaronson "Apakah P Versus NP Secara Independen?"

Marzio De Biasi

Sepertinya saya bahwa Anda memiliki kebingungan yang lebih mendasar tentang bagaimana sesuatu bisa menjadi kenyataan tetapi tidak dapat dibuktikan. Silakan periksa tur dan pusat bantuan untuk cakupan situs ini. Saya pikir ini lebih cocok untuk Ilmu Komputer atau Matematika .

Kaveh

makalah semi-terkenal ini Bukti- bukti alami oleh Razborov / Rudich berlaku untuk pertanyaan ini

vzn

Anda juga mungkin tertarik pada monografi Hartmanis "Komputasi Layak dan Properti Kompleksitas yang Dapat Dibuktikan" yang pada dasarnya membahas apa yang terjadi jika kita hanya mempertimbangkan masalah yang dapat dibuktikan dalam P, dapat dibuktikan dalam NP, dll.

Joshua Grochow

Jawaban:

Jika P = NP, harus ada algoritma polinomial-waktu untuk masalah NP-lengkap. Namun, mungkin tidak ada algoritma yang terbukti memecahkan masalah NP-lengkap dan terbukti berjalan dalam waktu polinomial.

David Richerby
sumber

Jadi, apa yang Anda katakan, apakah kekurangannya adalah bahwa mungkin ada contoh solusi polinomial tetapi Anda mungkin tidak dapat membuktikan bahwa itu polinomial? Karena itu tidak dipertimbangkan dalam contoh dengan contoh, jadi saya masih tidak melihat cacatnya.

Alvaro

Misalkan P = NP tetapi ini tidak dapat dibuktikan. Ini berarti ada algoritma waktu polinomial A untuk 3-SAT. Jika Anda dapat membuktikan bahwa A adalah algoritma poli-waktu untuk 3-SAT, itu akan bertentangan dengan unprovability dari P = NP. Oleh karena itu, walaupun benar bahwa A berjalan dalam waktu polinomial dan benar bahwa A memecahkan 3-SAT, setidaknya salah satu dari fakta ini tidak dapat dibuktikan. 3-SAT ada tidak menyiratkan bahwa "dapat ditemukan".

David Richerby

Jadi, "Tetapi jika tidak ada contoh solusi polinomial untuk masalah NP-complete dapat ditemukan, ini berarti bahwa P = NP salah" adalah salah, karena dapatkah ada solusi walaupun tidak dapat ditemukan?

Alvaro

Itu benar.

David Richerby

M

$M$

c

$c$

N

$N$

n \geq N

$n \geq N$

n

$n$

M

$M$

n^{c}

$n^c$

$\neq$

Tpecatte
sumber