Demostrando que si entonces

10

Realmente me gustaría su ayuda para demostrar lo siguiente.

Si entonces .NTime(n100)DTime(n1000)P=NP

Aquí, es la clase de todos los idiomas que puede decidir la máquina de Turing no determinista en el tiempo polinomial de y es la clase de todos los idiomas que puede decidir una máquina de Turing determinista en el tiempo polinomial de .NTime(n100)O(n100)DTime(n1000)O(n1000)

¿Alguna ayuda / sugerencia?

Joni
fuente
77
Sugerencia: relleno .
sdcvvc
¿De dónde se origina esta pregunta?
vzn

Respuestas:

3

Aquí está la solución usando relleno. Supongamos que . Defina un nuevo idioma . Cada corresponde a alguna de longitud . Por lo tanto, podemos decidir si en tiempo no determinista , es decir, . Para decidir si , forma y ejecuta el algoritmo determinista de tiempo paraLNTime(n1000)L={x0|x|10|x|:xL}xLyL|y|=|x|+(|x|10|x|)=|x|10yL|x|1000=|y|100LNTime(n100)DTime(n1000)xLy=x0x10|x||y|1000=|x|10000L. Concluimos que .LDTime(n10000)

Yuval Filmus
fuente
2

Divide el problema en dos partes:

  1. Hay un lenguaje completo en .NPNTime(n1000)
  2. Si un lenguaje completo está en entonces .NPDTime(n1000)PP=NP
Kaveh
fuente
-2

Esta es una consecuencia casi trivial de la definición de completitud NP. Si cualquier lenguaje en NP es solucionable en tiempo polinómico (lo cual es afirmado por la premisa), entonces todos lo son. Otra forma de ver esto es mirar el teorema de Cook para completar NP que reduce todos los lenguajes NP completos al reconocimiento de un lenguaje que involucra SAT y la conversión de la máquina de Turing no determinista en SAT.

vzn
fuente
3
Lo que usted dijo es cierto, pero de los idiomas NP completos (no idiomas NP). También tenemos que demostrar que existe un lenguaje NP completo que se puede resolver en verdadero, creo, pero no obvio por definición. NTime(n100)
SamM
de acuerdo, buen pt. ¿Crees que esto se sigue de los límites en la prueba de Cook ...? SAT puede convertir / resolver todas las máquinas NP en NTime ( , ...? nc)c<100
vzn
3
@vzn: No creo que podamos probar . Creo que podría estar contradiciendo uno de los teoremas de jerarquía ...c<100
Aryabhata
después de pensarlo un poco más cuidadosamente, de acuerdo. (mirada inicial, pensé que esta era una pregunta básica ...) la prueba de cocina crea un nuevo SAT que tiene un tamaño polinómico limitado en relación con la máquina original, pero la máquina inicial no tiene límites en el exponente polinómico (wrt esa prueba). si deduje una contradicción, entonces =) ... de todos modos, ¿tal vez estamos diciendo que esta es realmente una pregunta abierta? es decir, ¿no se sabe que sea verdadera o falsa la teoría existente? PNP
vzn
44
@vzn: La pregunta se puede resolver utilizando la técnica de relleno, aludida por sdcvvc.
Yuval Filmus