Est différent de ?

Pouvons-nous prouver que pour chaque langue qui n'est pas -hard (cela suppose ), ? Sinon, cela peut-il être prouvé sous des hypothèses raisonnables? $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
la source

Je pense que cette question a une réponse idiote: Soit , puis certainement une fois que vous supposez que . Vous pouvez donc vouloir, en supposant toujours , être dans et non -hard. [Edit: Oh, j'ai lu votre commentaire ci-dessous, donc votre question semble être: "Est-ce vrai que pour tous ces , l'inégalité se produit?", Plutôt que "Existe-t-il un tel ?" => Je modifie votre question!]

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$

Bruno

Réponses:

Dépend de votre définition de NPI. Si A est incomplète pour les réductions de Turing, la réponse est oui puisque SAT est pas dans . $P^A$

Si A est simplement incomplet, nous ne savons pas comment le prouver. Nous avons un monde relativisé avec un ensemble A dans NP tel que A n'est pas NP-complet via plusieurs réductions mais SAT peut être calculé par une seule requête à A. (Théorème 1.9 dans cet article ).

Lance Fortnow
la source

Voulez-vous dire Theorem 1.9?

Geoffrey Irving

Tu as raison. Fixé.

Lance Fortnow