Apakah

Bisakah kita membuktikan bahwa untuk setiap bahasa yang bukan -hard (ini mengasumsikan ), ? Bergantian, dapatkah ini dibuktikan dengan asumsi yang masuk akal? $L\in\mathsf{NP}$ $\mathsf{NP}$ $\mathsf P \ne \mathsf{NP}$ $\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$

cc.complexity-theory complexity-classes np-intermediate GMB
sumber

Saya pikir pertanyaan ini memiliki jawaban yang konyol: Let

, maka dipastikan

setelah Anda menganggap bahwa

. Jadi Anda mungkin ingin, masih mengasumsikan

berada di

dan bukan

. [Sunting: Oh, saya membaca komentar Anda di bawah, jadi pertanyaan Anda tampaknya adalah: "Apakah itu benar bahwa untuk semua

seperti itu , ketidaksetaraan terjadi?", Daripada "Apakah ada

seperti itu

L \in P \subseteq N P

$L\in\mathsf P\subseteq\mathsf{NP}$

P^{L} \neq P^{SAT}

$\mathsf P^L\neq \mathsf P^{\text{SAT}}$

P \neq N P

$\mathsf P\neq\mathsf{NP}$

P \neq N P

$\mathsf P\neq\mathsf{NP}$

L

$L$

N P ∖ P

$\mathsf{NP}\setminus\mathsf P$

N P

$\mathsf{NP}$

L

$L$

L

$L$ ? "=> Saya mengedit pertanyaan Anda!]

Bruno

Jawaban:

Tergantung pada definisi Anda tentang NPI. Jika A tidak lengkap untuk pengurangan Turing, jawabannya adalah ya karena SAT tidak dalam . $P^A$

Jika A hanya banyak-satu tidak lengkap maka kita tidak tahu bagaimana membuktikannya. Kami memiliki dunia yang ter-relativisasi dengan ada himpunan A di NP sehingga A tidak lengkap NP melalui reduksi banyak-satu tetapi SAT dapat dihitung dengan satu permintaan ke A. (Teorema 1.9 dalam makalah ini ).

Lance Fortnow
sumber

Apakah maksud Anda Teorema 1.9?

Geoffrey Irving

Kamu benar. Tetap.

Lance Fortnow