¿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.
Sé que la prueba donde se demuestra que existe un oráculo tal que P A ≠ N 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 A ≠ N P A pero donde sea que busque y lea, es "obvio" o "directo" en todas partes, pero no veo cómo demostrarlo en absoluto .
complexity-theory
relativization
Stewenson
fuente
fuente
Respuestas:
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=⋃nAn i i P Mi {x∣∃y∈A |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 mMi A 0m m Mi m Mi m Mi A m o menos se mantendrá igual). Esto asegura que no decida el idioma correctamente y complete la prueba.MAi
fuente
fuente