Masalah yang ada di P hanya jika P! = NP

Apakah ada masalah yang dapat dipecahkan dalam waktu polinomial hanya jika P! = NP, dan sebaliknya dipecahkan dalam waktu (katakanlah) waktu? $O(2^n)$

Contoh sederhana adalah: Jika P! = NP, hitung tes primality untuk angka n-bit acak, jika tidak, evaluasi posisi kasus terburuk acak dalam catur umum papan nxn dengan potongan 2n di setiap sisi. Itu tampaknya agak berantakan. Apakah ada contoh yang lebih alami?

cc.complexity-theory reference-request Phylliida
sumber

Tidak persis apa yang Anda tanyakan, tetapi ada koneksi antara batas bawah sirkuit (misalnya SAT membutuhkan sirkuit ukuran super-polinomial, menyiratkan terutama bahwa P! = NP) dan derandomisasi (misalnya BPP = P, khususnya beberapa masalah baru akan menjadi diketahui berada di P). Tapi saya cukup yakin bahwa P! = NP bukan asumsi yang cukup kuat untuk hasil seperti itu.

usul

Jika

dapat dibuktikan dalam ZFC (masalah terbuka) maka suatu algoritme dapat berupa: pada input

, jika

tidak menyandikan bukti valid dari

maka ouput

sebaliknya mensimulasikan mesin Turing

pada pita kosong untuk

langkah dan keluaran

jika ditolak atau tidak berhenti,

sebaliknya.

P \neq N P

$P\neq NP$

x

$x$

x

$x$

P \neq N P

$P\neq NP$

0

$0$

x

$x$

2^{| x |}

$2^{|x|}$

0

$0$

1

$1$

Marzio De Biasi

Bagaimana kalau itu terbukti di HoTT tetapi tidak ZFC?

Chad Brewbaker

@MarzioDeBiasi Itu benar, terima kasih, dan benar-benar seperti yang ditunjukkan Chad, Anda dapat menggunakan set aksioma apa pun sebagai pengganti ZFC, semoga menggunakan yang konsisten yang dapat membuktikan dengan cara yang bermakna bahwa P! = NP. Itu masih terasa sangat aneh, maksud saya seperti contoh saya kita dapat dengan mudah mengganti

dengan kompleksitas waktu lain yang diinginkan (termasuk, katakanlah, menyelesaikan masalah penghentian).

2^{[} | x |]

$2^[|x|]$

Phylliida

Mungkin tidak ada contoh yang terlihat alami dari tipe yang saya minta, tetapi sepertinya definisi formal "alami" (katakanlah, probabilitas tinggi untuk memilih masalah ini mengingat masalah acak dalam semua masalah dalam EXP) agak kalah pada beberapa makna jadi mungkin tidak terlalu berarti untuk mencoba dan membuktikan itu, saya tidak yakin.

Phylliida

Masalah yang ada di P hanya jika P! = NP

Jawaban: