Un oráculo para separar NP de coNP

12

¿Cómo demostrar que ? Solo estoy buscando un oracle TM M y un lenguaje recursivo L ( M ) = L para el cual esto es válido.NPAcoNPAML(M)=L

Sé que la prueba donde se demuestra que existe un oráculo tal que P AN P A y un oráculo Un tal que P A = N P A . Tengo una pista de que debería encontrar tal oráculo A extendiendo la prueba de P AN P A pero donde sea que busque y lea, es "obvio" o "directo" en todas partes, pero no veo cómo demostrarlo en absoluto .APANPAAPA=NPAAPANPA

Stewenson
fuente
66
No está claro si ha seguido la pista. Me sorprende escuchar que es obvio, pero puede encontrar la prueba en (por ejemplo) Complejidad computacional: un enfoque moderno de Arora y Barak. PANPA

Respuestas:

9

Como Max dijo que la modificación no es difícil, sugiero que usted no lee el resto de esta respuesta y pensar en el problema un poco más, sólo hay una parte que necesita modificación y recordando la definición de cuándo un la máquina acepta lo ayudará a arreglar esa parte.coNP

Explicaré la modificación requerida a continuación, pero primero veamos brevemente la prueba original.

En la prueba original se construye por etapas, donde en el paso i con asegurarse de que i ª máquina en P , M i , no determina el idioma { x | y A | x | = | y | } correctamente. Tenga en cuenta que el conjunto está en N P A .A=nAniiPMi{xyA |x|=|y|}NPA

Logramos esto simulando usando la parte de A que hemos construido en un 0 m donde m es lo suficientemente grande (la cadena es más larga que las cadenas consideradas en los pasos anteriores). M i acepta, no añadimos nada, si rechaza añadimos una serie de longitud m que M i no hace que una consulta al conjunto (existe tal una cadena, ya que hay muchos exponencialmente cadenas de longitud m , pero M i no puedo preguntar sobre todos ellos en tiempo polinómico). No modificaremos esta parte de A en pasos futuros (es decir, cadenas de longitud mMiA0mmMimMimMiAmo menos se mantendrá igual). Esto asegura que no decida el idioma correctamente y complete la prueba.MiA

Ahora, se supone que las máquinas estuviera en c o N P en lugar de P . Tenemos que modificar la prueba para asegurarse de que M A i no reconocerá L . Si acepta, mantenemos A como antes y todo funciona bien como en la prueba original. Si se rechaza, necesitamos agregar una cadena al conjunto para asegurarnos de que no responda correctamente. Todavía podemos simular M i con la parte de A que tenemos, el problema es que M i puede consultar todas las cadenas de longitud n . Aquí el camino a c oMicoNPPMiALAMiAMin máquina N P funciona se vuelve importante. Acepta si y solo sitodas lasrutas de cálculo aceptan. Como se rechaza en este caso, hay una ruta de cálculo que se rechaza. Mientras mantengamos este camino intacto, todo funcionará, por lo que solo necesitamos mantener las respuestas a las consultas en ese camino igual. El número de consultas en esta ruta es polinomial (ya que la máquina se ejecuta en tiempo polinomial), por lo que hay cadenas de longitud m que la ruta no consulta, solo agregue una de ellas a A y el resto de la prueba funciona como antes de.coNPmA

ADSpace(nω(1))

Kaveh
fuente
3

PA=NPAPBNPBAB

Vincent Russo
fuente