Apa konteks aksiomatik (teori himpunan) P vs NP dan NP = EXPTIME dugaan?

Ketika dugaan atau diatur (misalnya oleh Clay Mathematical Institute oleh S. Cook, lihat di sini ) sistem aksiomatik matematika apa yang diasumsikan? $\mathbf{P} = \mathbf{NP}$ $\mathbf{P} \neq \mathbf{NP}$

Untuk membuktikan atau menyangkal pernyataan seperti itu, Anda perlu mengasumsikan beberapa aksioma. Yang mana Hanya aritmetika Peano (bahasa formal orde kedua)? The Zermelo-Fraenkel set teori dengan aksioma pilihan? Teori himpunan aksiomatik yang lebih kecil (misalnya perangkat konstruktif Gödel, di mana hipotesis kontinum juga berlaku, lihat di sini )?

Jelas, itu harus menjadi teori aksiomatik yang menerima tak terhingga yang dapat dihitung. Tapi yang mana khususnya? Apakah ada hasil yang dipublikasikan yang akan membuktikan mereka konsisten dalam teori himpunan aksiomatik tertentu? (Dengan kata lain, mendefinisikan model yang benar, tetapi tidak mengklaim benar dalam semua model).

cc.complexity-theory model-theory Constantine Kyritsis
sumber

umumnya didasarkan pada model TM yang belum terbukti memiliki ketergantungan khusus pada pilihan aksioma teori himpunan ... sejauh ini!

vzn

D T I M E (n^{α (n)})

$\mathsf{DTIME}(n^{\alpha(n)})$

α (n)

$\alpha(n)$

lihat juga hasil TCS independen ZFC yang menunjukkan kira-kira "tidak terlalu jauh" ...

vzn

Π_{1}^{0}

$\Pi^0_1$

P \neq N P

$P\neq NP$

S A T

$SAT$

Π_{1}^{0}

$\Pi^0_1$ secara umum .

Damiano Mazza

@ DamianoMazza Terima kasih Damiano, Anda benar, permintaan maaf karena membuat klaim yang sangat kuat.

Sasho Nikolov

Jawaban:

Itu tidak ditentukan. Ketika ada kertas kandidat yang cukup serius yang mengaku menyelesaikan P ≟ NP, Komite Penasihat Khusus akan dibentuk untuk memutuskan apakah (dan kepada siapa) akan memberikan hadiah. Saya berasumsi bahwa Komite Penasihat Khusus akan memutuskan apakah sistem aksioma Anda dapat diterima. Jika Anda menganggap ZF dengan pilihan, saya jamin mereka akan menerimanya. Jika Anda menganggap P ≠ NP sebagai aksioma, saya jamin mereka tidak akan melakukannya.

Peter Shor
sumber

Akan sangat menarik / aneh jika diperlukan pilihan untuk pembuktian (yaitu ZFC berfungsi, ZF tidak).

usul

Saya berterima kasih kepada orang-orang atas jawaban mereka sejauh ini. Masuk akal bahwa itu tidak ditentukan dan itu adalah variabel yang diasumsikan sistem aksiomatik (teori set). Tampak bagi saya bahwa dalam teori himpunan aksiomatik yang sangat restriktif (atau model restriktif teori himpunan aksiomatik) lebih memungkinkan seseorang dapat membuktikan bahwa NP = EXPTIME dan dalam lebih pluralistik (sistem aksiomatik atau model teori himpunan) lebih mungkin bahwa NP bukan EXPTIME (nilai perbedaan kompleksitas yang lebih halus).

Constantine Kyritsis

Dan bahkan mungkin terjadi bahwa seseorang dapat datang dengan bukti, bahwa di dalam Peano Aritmatika (dengan himpunan dapat didefinisikan dari rumus logis hanya tanpa aksioma teori himpunan) dugaan yang terkenal independen dan tidak dapat dibuktikan (Kecuali jika sudah ada hasil tentang dugaan ini di dalam Aritmetika Peano atau argumen ketidakmungkinan yang lebih sederhana yang saya tidak tahu).

Constantine Kyritsis

Tidak ada yang berpikir serius bahwa P! = NP tidak tergantung pada ZFC. Kami tidak mengetahui adanya pernyataan matematis yang tidak dibuat-buat yang tidak tergantung pada ZFC (selain dari yang sudah jelas Godelian). Hasil ini tidak akan terjadi.

David Harris

@ Usul: Ini bukan hanya aneh, itu sebenarnya tidak mungkin. ZFC konservatif atas ZF untuk pernyataan aritmatika.

Emil Jeřábek