Kompleksitas Bukti dari Bukti atau Penonaktifan P = NP

Apakah ada penelitian tentang kompleksitas bukti dari resolusi untuk masalah P = NP? Jika tidak, mengingat kurangnya kemajuan pada masalah, apakah tidak masuk akal untuk menduga bahwa bukti apa pun yang menyelesaikan masalah P = NP akan memerlukan sejumlah langkah super polinomial?

Diketahui bahwa setiap bukti sirkuit super-polinomial batas bawah (yang merupakan pernyataan sedikit lebih kuat dari ) memerlukan super-polinomial, bahkan bukti ukuran eksponensial dalam sistem bukti lemah seperti resolusi. Generalisasi ini ke sistem bukti yang lebih kuat adalah masalah terbuka yang terkenal.$P\neq NP$

Lihat bagian 5 survei ini oleh A. Razborov di mana hal-hal ini ditunjukkan.

Kompleksitas bukti hanya masuk akal ketika ada urutan pernyataan tergantung pada parameter . Sebagai contoh, proposisi P H P n menyatakan (secara informal) bahwa tidak ada penambangan [ n + 1 ] → [ n ] . Urutan proposisi ini sulit untuk sistem bukti proposisional tertentu.$n$$\mathsf{PHP}_n$$[n+1] \to [n]$

Pernyataan adalah pernyataan tunggal, jadi Anda tidak dapat menerapkan kompleksitas bukti secara langsung. Namun, urutan pernyataan berikut ini masuk akal, untuk fungsi-fungsi tertentu s ( n ) : "tidak ada rangkaian ukuran s ( n ) dengan benar menyelesaikan SAT untuk instance panjang n ". Ini telah dipertimbangkan dalam literatur, misalnya oleh Razborov (yang menganggap pengaturan kompleksitas bukti seragam, yaitu aritmatika terbatas).$\mathsf{P} \neq \mathsf{NP}$$s(n)$$s(n)$$n$

Kami memiliki 3 kasus:

• Ada ada bukti bahwa . Daripada ada algoritma yang memecahkan masalah "Keluarkan bukti bahwa P = N P " yang berjalan dalam O ( 1 ) waktu. Ini mengkode-kode bukti di Turing Machine itu sendiri, dan memancarkannya. Ini berjalan dalam waktu yang sama tidak peduli inputnya.$P = NP$$P=NP$$O(1)$

• Demikian pula, jika ada bukti bahwa , maka kita dapat menulis sebuah algoritma yang memancarkan bukti ini dalam waktu O ( 1 ) .$P\neq NP$$O(1)$

• $O(\infty)$

Hanya karena kami belum menemukan bukti apa pun, tidak berarti tidak ada, dan kelas kompleksitas ditentukan berdasarkan apa yang ada.

$P=NP$

Apa yang kita ketahui adalah bahwa, secara umum, masalah "Ambil pernyataan dalam logika Predikat dan tentukan apakah ada bukti untuk itu" tidak dapat diputuskan. Jadi tidak ada prosedur pembuatan bukti generik yang dapat kita gunakan untuk menghubungkan P vs NP, yang dijamin akan memberikan hasil.

Jika P = NP maka yang perlu Anda lakukan adalah membuat algoritma waktu polinomial untuk menyelesaikan beberapa masalah NP-complete, dan membuktikan bahwa itu memang polinomial (yang mungkin sulit, misalnya algoritma Simplex biasanya berjalan sangat cepat tetapi membuktikan bahwa itu berjalan cepat sepertinya sangat sulit).

$n^{100}$