Ist

Können wir beweisen, dass für jede Sprache , die nicht -hart ist (dies setzt voraus ), ? Kann dies alternativ unter vernünftigen Annahmen nachgewiesen werden? $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
quelle

Ich denke , diese Frage eine dumme Antwort hat: Sei

, dann sicherlich

, wenn Sie davon ausgehen , dass

. Unter der Annahme, dass

und nicht in

-hard ist, möchten Sie vielleicht . [Bearbeiten: Oh, ich habe Ihren Kommentar unten gelesen, also scheint Ihre Frage zu lauten: "Trifft das zu, dass für all dieses

die Ungleichung auftritt?", Und nicht "Gibt es ein solches

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$ ? "=> Ich bearbeite Ihre Frage!]

Bruno

Antworten:

Hängt von Ihrer Definition des NPI ab. Wenn eine unvollständige für Turing Reduzierungen ist, ist die Antwort ja , da SAT nicht in ist . $P^A$

Wenn A nur um ein Vielfaches unvollständig ist, wissen wir nicht, wie wir es beweisen sollen. Wir haben eine relativierte Welt, in der es eine Menge A in NP gibt, so dass A nicht über Vielfachreduktionen NP-vollständig ist, sondern SAT durch eine einzelne Abfrage an A. berechnet werden kann (Satz 1.9 in diesem Artikel ).

Lance Fortnow
quelle

Meinen Sie Theorem 1.9?

Geoffrey Irving

Du hast recht. Fest.

Lance Fortnow