¿Prueba incorrecta de primer nivel de la jerarquía polinómica colapso?

Question

Soy un estudiante de CS y puedo participar en TCS.SE. Estoy teniendo problemas para encontrar el error en una prueba sobre el polinomio de la jerarquía de colapso para el primer nivel ($NP = coNP$). Creo que el razonamiento es falso, porque es muy simple y podría ser de conocimiento común, sin embargo no lo es.

Deje $M$ ser cualquier oracle TM en $NP^{NP}$ ( $ \Sigma^{P}_{2} $ ) . Obviamente, haciendo caso omiso de su oráculo, $M$ puede resolver cualquier problema en NP.

En el otro (y más importante), la dirección, deje $M'$ ser un TM, donde en lugar de utilizar el de oracle, se codifican en un simple no-determinista de la máquina con un tiempo de ejecución de $NTIME( k(n) )$. Si $M$ tuvo un tiempo de ejecución de $NTIME( p(n) )$ , $M'$ tendrá un tiempo de ejecución de $NTIME( p(n)*k(n) )$ cual es el polinomio. Por lo tanto, para cualquier oracle TM en $NP^{NP}$, hay un no-determinista TM que puede resolver el mismo problema en el polinomio de tiempo. De ello se desprende que $NP^{NP} /subset NP$.

Mediante la combinación de las dos declaraciones que tienen que $NP=NP^{NP}$ y la ampliación de este, $NP=coNP=P^{NP}=NP^{NP}$ y el polinomio de jerarquía se derrumba para el 1er nivel.

¿Dónde está el error en la anterior prueba?

Answer 1

Si combinas un oráculo de NP con una máquina de NP no conseguir otra máquina de NP. La forma más fácil de ver que es consultar el oráculo una vez y responder a la negación - esta máquina es claramente co-NP y no NP.

Si usted toma una general $NP^{NP}$ máquina, necesita cuantificar existencialmente y universalmente. Esto es muy lúcidamente explica en estas notas de la Conferencia.

Answer 2

Si desea convertir el $NP^{NP}$ TM a un $NP$ TM se debe verificar cada respuesta de oracle en una máquina de $NP$. Respuestas 'Sí' es fácil porque es un oráculo de $NP$. Pero si usted quiere comprobar una respuesta 'No' tienes que comprobar que para cada elección no determinista dentro de la máquina de oracle la respuesta es 'No'. Esto no puede funcionar a menos que $NP = coNP$.