Daftar teorema yang menyatakan bahwa P tidak sama dengan NP jika dan hanya jika

18

Saya pikir itu akan menjadi ide yang baik untuk membuat daftar teorema yang menyatakan bahwa P tidak sama dengan NP jika dan hanya jika ini dan itu keluar, beberapa kelas kompleksitas terkandung dalam kelas kompleksitas lain dan seterusnya dan seterusnya.

cc.complexity-theory big-list p-vs-np Tayfun Pay
sumber

15

Itu akan menjadi fraksi konstan dari semua makalah kompleksitas!

MCH

5

Saya akan mengatakan: "daftar kondisi menyiratkan P? NP", karena tidak semua teorema itu adalah "jika dan hanya jika". Juga, saya kira orang lebih tertarik - secara umum - untuk mengetahui bagaimana membuktikan P? NP dengan membuktikan sesuatu yang lain, daripada mendaftar banyak konsekuensi dari hasil ini, sebuah topik yang telah banyak dibahas di tempat lain.

Janoma

2

@Janoma: jika Anda ingin membatasi diri Anda pada implikasi, maka daftarnya akan sangat besar, mengingat sejumlah besar hasil formulir: "Jika P! = NP, maka masalah X tidak dapat diselesaikan dengan tepat / didekati dalam faktor konstan dalam waktu polinomial ". Pertanyaannya harus jauh lebih fokus atau lebih baik jika kita ingin menghindarinya.

Anthony Labarre

4

@ Janoma: Itu tidak menyelesaikan keprihatinan Anthony yang beralasan. Hipotesis yang menyiratkan P = NP hanyalah negasi dari konsekuensi P ≠ NP, dan hipotesis yang menyiratkan P ≠ NP adalah negasi dari konsekuensi P = NP. Jika SAT dapat dipecahkan dalam waktu polinomial, maka P = NP. Jika Max3SAT diperkirakan polinomial-waktu dalam faktor konstan kurang dari 8/7, maka P = NP. Dan seterusnya.

Tsuyoshi Ito

7

@ Janoma: "Jika X maka P = NP" sama dengan "Jika P ≠ NP maka tidak-X".

Jeff

11

Ini satu:

Teorema Mahaney: Tidak ada set NP-lengkap yang jarang jika dan hanya jika (dalam pengurangan Karp). $P \ne NP$

Yang lain adalah:

$P \ne NP$ jika dan hanya jika $P \ne PH$

Mohammad Al-Turkistany
sumber

Mungkin ini mudah: jika dan hanya jika .

P \neq N P

$P \ne NP$

F P \neq F N P

$FP \ne FNP$

Mohammad Al-Turkistany

11

$P \ne NP$ jika dan hanya jika fungsi satu arah terburuk terjadi.

Referensi:

Alan L. Selman. Sebuah survei fungsi satu arah dalam teori kompleksitas. Teori sistem matematika, 25 (3): 203–221, 1992.

Mohammad Al-Turkistany
sumber

1

seorang ref akan baik

vzn

Apakah kamu yakin Saya belum pernah mendengar OWF kasus terburuk sebelumnya, tetapi dari catatan di sini sepertinya keberadaan mereka setara dengan .

B P P \neq N P

$BPP \neq NP$

Huck Bennett

Ya saya yakin. :) Lihat referensi.

Mohammad Al-Turkistany

8

Berikut ini adalah hasil dari teori kompleksitas deskriptif:

$P \ne NP$ jika dan hanya jika beberapa properti urutan kedua tidak dapat diungkapkan menggunakan logika urutan pertama plus titik tetap paling sedikit.

Referensi: Immerman, Bahasa yang menangkap kelas kompleksitas

Mohammad Al-Turkistany
sumber

... pada struktur yang dipesan. Kalau tidak, kita tahu tanpa syarat bahwa properti seperti itu ada.

Emil Jeřábek mendukung Monica

@ EmilJeřábek ya, pada struktur yang dipesan seperti yang secara implisit diasumsikan oleh Immerman di atas kertas.

Mohammad Al-Turkistany

7

Teorema Ladner dapat dinyatakan sebagai:

$P \ne NP$ jika dan hanya jika ada set tidak lengkap di . $NP-P$

Set tidak lengkap adalah set yang tidak lengkap untuk dalam banyak waktu pengurangan polinomial. $NP$

Referensi

Teori Kompleksitas dan Kriptologi: Pengantar Cryptocomplexity Oleh Jörg Rothe, halaman 106

Mohammad Al-Turkistany
sumber

Daftar teorema yang menyatakan bahwa P tidak sama dengan NP jika dan hanya jika

Jawaban: