como oráculo

12

¿ NPNPcoNP=NPmantener?

Claramente NPNPNP , pero me parece que NPcoNP es "determinista", lo que me hace creer que esto es cierto.

¿Hay una prueba simple (o tal vez solo por definición)?

maomao
fuente
66
Primero si. De hecho, un oráculo A satisface NPA=NP si y sólo si ANPcoNP . Esta clase se llama Low(NP) o, a veces, L1P : complexzoo.uwaterloo.ca/Complexity_Zoo:L#lkp . En segundo lugar, no creo que esté del todo claro que NPNPNP , aunque esta es una creencia muy extendida. En particular, implica y parece ser estrictamente más fuerte, ya que no hay implicación relativizable a la inversa. PNP
Joshua Grochow
2
Además, las personas que creen que FACTORAR es difícil pueden estar en desacuerdo con su intuición de que es "determinista". NPcoNP
Niel de Beaudrap
99
@JoshuaGrochow: Creo que deberías agregar eso como respuesta, con alguna exposición sobre cuáles son las clases en la jerarquía baja; es una respuesta tan buena como es probable que obtenga el OP.
Niel de Beaudrap
2
NPNPcoNPNP
44
@NieldeBeaudrap: Mi vacilación al publicarlo como respuesta en lugar de comentario fue que, aunque creo que maomao realmente hizo esta pregunta en serio, puede ser, y ha sido en el pasado, dada como un ejercicio de tarea.
Joshua Grochow

Respuestas:

13

ANPA=NPANPcoNPLow(NP)L1P

P=NPcoNPAPNPA=NPANPANPcoNP

NPA=NPANPcoNP

Joshua Grochow
fuente