Demostrando que si entonces

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

Si entonces .$\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$$\mathrm{P}=\mathrm{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 .$\mathrm{NTime}(n^{100})$$O(n^{100})$$\mathrm{DTime}(n^{1000})$$O(n^{1000})$

¿Alguna ayuda / sugerencia?

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 para$L \in \mathrm{NTime}(n^{1000})$$L' = \{x0^{|x|^{10}-|x|} : x \in L\}$$x \in L$$y \in L'$$|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$$y \in L'$$|x|^{1000} = |y|^{100}$$L' \in \mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$$x \in L$$y = x0^{x^{10}-|x|}$$|y|^{1000} = |x|^{10000}$$L'$. Concluimos que .$L \in \mathrm{DTime}(n^{10000})$

Divide el problema en dos partes:

1. Hay un lenguaje completo en .$\mathsf{NP}$$\mathsf{NTime}(n^{1000})$
2. Si un lenguaje completo está en entonces .$\mathsf{NP}$$\mathsf{DTime}(n^{1000}) \subset \mathsf{P}$$\mathsf{P}=\mathsf{NP}$

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.