¿Es

12

¿Podemos demostrar que para cada idioma que no es N P -duro (esto supone PN P ), P LP SAT ? Alternativamente, ¿se puede probar esto bajo cualquier supuesto razonable?LNPNPPNPPLPSAT

GMB
fuente
Creo que esta pregunta tiene una respuesta tonta: Let , entonces, ciertamente, P LP SAT una vez que asuma que PN P . Por lo tanto, es posible que desee, suponiendo que PN P , L esté en N PP y no en N P -duro. [Editar: Oh, leí tu comentario a continuación, por lo que tu pregunta parece ser: "¿Es cierto que para todos esos L , la desigualdad ocurre?", En lugar de "¿Existe tal LLPNPPLPSATPNPPNPLNPPNPLL? "=> ¡Edito tu pregunta!]
Bruno

Respuestas:

16

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 .PA

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