Mengapa masalah NPI tidak semuanya memiliki kompleksitas yang sama?

Bagaimana seseorang melihat suatu masalah dan alasan bahwa itu kemungkinan NP-Intermediate dibandingkan dengan NP-Complete? Seringkali cukup sederhana untuk melihat suatu masalah dan mengatakan apakah itu mungkin NP-Complete atau tidak, tetapi bagi saya tampaknya lebih sulit untuk mengatakan apakah suatu masalah adalah NP-Intermediate karena garis tampaknya cukup tipis antara keduanya. kelas. Pada dasarnya yang saya tanyakan adalah mengapa masalah yang dapat diverifikasi dalam waktu polinomial (jika sama sekali) tetapi tidak diselesaikan dalam waktu polinomial (selama P dos't sama dengan NP) bukan waktu polinomial yang dapat direduksi satu sama lain. Juga, apakah ada cara untuk menunjukkan masalah apakah NP-Intermediate mirip dengan bagaimana masalah ditunjukkan sebagai NP-Hard, seperti reduksi atau teknik lainnya? Tautan atau buku teks apa pun yang akan membantu saya memahami kelas NP-Menengah akan dihargai juga.

cc.complexity-theory complexity-classes np-intermediate Jesse Stern
sumber

"masalah yang dapat dipenuhi dalam waktu polinomial", saya kira maksud Anda "masalah yang dapat diverifikasi dalam polinomial waktu".

Kaveh

Ada kelas masalah GI-lengkap yang secara polinomi setara dengan Grafik Isomorfisme. GI adalah masalah besar yang diduga sebagai perantara-NP

Mohammad Al-Turkistany

Btw, judulnya menyesatkan, kesetaraan dua masalah kompleksitas sehubungan dengan pengurangan (misalnya pengurangan Karp) sudah ditentukan, saya sarankan Anda mengubahnya menjadi sesuatu seperti "Mengapa masalah NPI tidak semuanya memiliki kompleksitas yang sama?".

Kaveh

@kaveh Melakukan semua pengeditan. Terima kasih atas jawaban hebat lainnya!

Jesse Stern

"Sering kali cukup sederhana untuk melihat masalah dan mengatakan apakah itu kemungkinan NP-Lengkap atau tidak". IMHO, itu tidak mungkin lebih jauh dari kebenaran!

Mahdi Cheraghchi

Jawaban:

Anda tidak dapat menunjukkan bahwa masalahnya adalah tanpa memisahkan dari . $\mathsf{NPI}$ $\mathsf{P}$ $\mathsf{NP}$

Ada masalah buatan yang dapat dibuktikan berada di menggunakan generalisasi teorema Lander (lihat juga ini ) dengan asumsi bahwa . $\mathsf{NPI}$ $\mathsf{NP}\neq\mathsf{P}$

Juga versi empuk dari masalah yang $\mathsf{NEXP\text{-}complete}$ $\mathsf{NPI}$ dengan asumsi (lihat juga ini dan ini ). $\mathsf{NEXP} \neq \mathsf{EXP}$

Masalah dalam sering sebagai ketika: $\mathsf{NP}$ $\mathsf{NPI}$

kami dapat menunjukkan dengan asumsi yang masuk akal bahwa itu bukan namun itu tidak diketahui berada di , $\mathsf{NPC}$ $\mathsf{P}$
kami dapat menunjukkan dengan asumsi yang masuk akal bahwa itu tidak ada di namun tidak diketahui berada di , $\mathsf{P}$ $\mathsf{NPC}$

dan kadang-kadang ketika kita tidak dapat menunjukkan bahwa itu ada di atau . $\mathsf{NPC}$ $\mathsf{P}$

Contoh asumsi yang masuk akal adalah hipotesis waktu eksponensial (atau beberapa asumsi kekerasan komputasi lainnya ).

Pada dasarnya yang saya tanyakan adalah mengapa masalah yang dapat dipenuhi dalam waktu polinomial (jika sama sekali) tetapi tidak diselesaikan dalam waktu polinomial (selama P tidak sama dengan NP) bukan waktu polinomial yang dapat direduksi satu sama lain.

Saya tidak mengerti mengapa orang berharap itu benar. Tetapi bagaimanapun juga, dengan asumsi itu mengikuti dari teorema Lander bahwa ada banyak tingkatan -degree antara dan . $\mathsf{NPC}\not \subseteq \mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{NP}$

Kaveh
sumber

"2. kita dapat menunjukkan di bawah asumsi yang masuk akal bahwa itu tidak dalam P namun itu tidak diketahui berada di NP" Bukankah maksudmu "... dalam NPC"?

Tyson Williams

@ Viktor, tidak, tidak diketahui bahwa tidak sama dengan , dan mereka berbeda iff dan berbeda. Putar kembali hasil edit Anda.

P

$\mathsf{P}$

N P C

$\mathsf{NPC}$

P

$\mathsf{P}$

N P

$\mathsf{NP}$

Kaveh

@ Kaveh, saya pikir dia sedang memikirkan bahasa-bahasa yang sepele ( dan ), tetapi Anda mengecualikannya dari P.

\emptyset

$\emptyset$

{0, 1}^{*}

$\{0,1\}^*$

didest

@Diego, well, tidak ada yang dapat direduksi untuk mereka, tetapi Anda benar. Saya akan memperbaikinya.

Kaveh

@ Kaveh dan Diego: Ya, saya sedang memikirkan bahasa-bahasa sepele ini.

Victor Stafusa

Kasus tipikal adalah ketika masalah di juga terletak pada atau . Dengan asumsi bahwa hierarki polinom tidak runtuh, masalah seperti itu tidak dapat -complete. Contohnya termasuk faktorisasi bilangan bulat, logaritma diskrit, isomorfisme grafik, beberapa masalah kisi, dll. $\mathsf{NP}$ $\mathsf{coNP}$ $\mathsf{coAM}$ $\mathsf{NP}$

Mahdi Cheraghchi
sumber

Kasus khas lain dari masalah adalah ketika ada saksi panjang tetapi lebih kecil dari . Masalah keberadaan klik ukuran dalam grafik adalah contoh khas - dalam hal ini, saksi (klik spesifik) membutuhkan bit . $NPI$ $\omega(\log n)$ $n^{O(1)}$ $\log n$ $O(\log^2 n)$

Dengan asumsi Hipotesis Waktu Eksponensial, masalah seperti itu lebih mudah daripada masalah lengkap (yang membutuhkan waktu ) tetapi lebih sulit daripada masalah waktu polinomial. $NP$ $\exp(n^{O(1)})$

David Harris
sumber