¿Es

¿Podemos demostrar que para cada idioma que no es -duro (esto supone ), ? Alternativamente, ¿se puede probar esto bajo cualquier supuesto razonable? $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
fuente

Creo que esta pregunta tiene una respuesta tonta: Let

, entonces, ciertamente,

una vez que asuma que

. Por lo tanto, es posible que desee, suponiendo que

esté en

y no en

-duro. [Editar: Oh, leí tu comentario a continuación, por lo que tu pregunta parece ser: "¿Es cierto que para todos esos

, la desigualdad ocurre?", En lugar de "¿Existe tal

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$ ? "=> ¡Edito tu pregunta!]

Bruno

Respuestas:

Depende de su definición de NPI. Si A es incompleta para las reducciones de Turing, la respuesta es sí, ya SAT no está en . $P^A$

Si A es solo uno incompleto, entonces no sabemos cómo demostrarlo. Tenemos un mundo relativizado con un conjunto A en NP tal que A no es NP completo a través de muchas reducciones, pero SAT puede calcularse mediante una sola consulta a A. (Teorema 1.9 en este documento ).

Lance Fortnow
fuente

¿Te refieres al teorema 1.9?

Geoffrey Irving

Tienes razón. Fijo.

Lance Fortnow