¿Por qué no podemos voltear la respuesta de un NDTM de manera eficiente?

Leí varias veces que no es posible cambiar la respuesta de un NDTM de manera eficiente. Sin embargo, no entiendo por qué. Por ejemplo, dado un NDTM que se ejecuta en O ( n ) , este texto (sección 3.3) establece que no está claro cómo otro NDTM T puede determinar en O ( n 100 ) tiempo cómo voltear la respuesta de $M$$O(n)$$T$$O(n^{100})$$M$

Mi problema es el siguiente: un NDTM genera si existe una secuencia de elecciones no deterministas que conducen al estado de aceptación. Además, existe un NDTM N U universal que puede simular cada NDTM con solo una pequeña sobrecarga (logarítmica). Entonces, ¿por qué no podemos construir T de la siguiente manera: Primero, simule M con el NDTM universal que debería ser posible en el tiempo O ( n log n ) . Luego, salida 1: la respuesta de M. Esto significaría que podemos voltear la respuesta de cualquier NDTM lineal en el tiempo O ( n log n ) .$1$$NU$$O(n\log n)$$O(n\log n)$

Una máquina de Turing no determinista acepta si al menos una ruta acepta; solo rechaza si todos los caminos rechazan. Esta asimetría hace que sea difícil "voltear las respuestas".

Por ejemplo, suponga que tiene una máquina Turing no determinista  que tiene dos rutas para la entrada  w : una acepta y la otra rechaza. M  tiene al menos una ruta de aceptación para  w , por lo que acepta. Supongamos que queremos producir una máquina que acepte exactamente las entradas que M  rechaza. El primer intento obvio es tomar  M y hacer que sus estados de aceptación rechacen, y sus estados de aceptación acepten. M  tiene una ruta de aceptación para  w y una ruta de rechazo; Esta nueva máquina  M ' tiene una ruta de rechazo y una ruta de aceptación. ¡Entonces todavía acepta  w , que se suponía que debía rechazar!$M$$w$$M$$w$$M$$M$$M$$w$$M'$$w$

Una máquina no determinista no puede ver todas sus rutas simultáneamente y tomar medidas basadas en lo que hacen todas esas rutas. Si lo desea, puede considerarlo como una forma de paralelismo en el que los hilos tienen prohibido comunicarse entre sí. Cuando todos los hilos hayan terminado, el programa debe hacerse la siguiente pregunta: "¿Al menos uno de mis hilos aceptó?" Si la respuesta es sí, está legalmente obligado a aceptar; Si la respuesta es no, está legalmente obligado a rechazar. No puede hacer nada más.

Cuando simula una máquina no determinista  usando otra, M ' , cada ruta de  M ' simula una ruta de  M y solo ve esa ruta. No puede decir, "Si todos esos otros caminos fueron rechazados, aceptaré" porque no puede ver los otros caminos; solo puede verse a sí mismo. Entonces, todo lo que podría decir es cosas como: "Si la ruta que simulé aceptó, la rechazaré" o "Si la ruta que simulé aceptó, aceptaré también". Luego, al final del cálculo, la máquina tiene que decir: "Si alguno de mis caminos lo acepta, yo también lo aceptaré", lo que lleva al problema que describí anteriormente. Para invertir el comportamiento de M , cada camino de M $M$$M'$$M'$$M$$M$$M'$necesita decir: "Si el camino que simulé aceptó, rechazo; de lo contrario, acepto" y, al final del cálculo, la máquina necesita decir: "Si todos mis caminos aceptaron, acepto; de lo contrario, rechazo ". Esto se debe a que, si todos los caminos del simulador aceptadas, es decir, todas caminos 's rechazados, por lo que M rechazada, por lo que las necesidades del simulador de aceptar. Pero el simulador no es una máquina de Turing no determinista válida porque no está utilizando el criterio de aceptación legalmente obligatorio. No puede hacer eso.$M$$M$

La única forma de saber si una máquina no determinista rechaza su entrada es probar todas las rutas posibles y verificar que todas rechacen. Después de todo, si incluso uno de ellos aceptara, la máquina aceptaría la entrada. Pero intentar cada ruta posible es exponencialmente más lento que probar solo una.

El problema es que los NDTM son intrínsecamente no simétricos: el tiempo significa que tienen O ( n ) pasos para adivinar una ruta de aceptación si existe, y rechazarán lo contrario (si no existe una ruta de aceptación).$O(n)$$O(n)$

El problema es que si su máquina está realmente en O ( n l o g ( n ) ) , significa que adivina en n l o g ( n ) un testigo de que M rechaza la entrada. Es posible que esto no sea posible, porque no hay testigos de rechazo de M , solo testigos de aceptación. El rechazo es la ausencia de testigos, por lo que no es fácil probar el rechazo en poco tiempo.$NU$$O(n log( n))$$n log (n)$$M$$M$

$\stackrel{?}{=}$$\stackrel{?}{=}$