Demostrando que si $ mathrm {ntime} (n^{100}) subseteq mathrm {dtime} (n^{1000}) $ entonces $ mathrm {p} = mathrm {np} $

Question

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

Si $ mathrm {ntime} (n^{100}) subseteq mathrm {dtime} (n^{1000}) $ entonces $ mathrm {p} = mathrm {np} $.

Aquí, $ Mathrm {ntime} (n^{100}) $ es la clase de todos los idiomas que se pueden decidir por una máquina de turing no determinista en tiempo polinomial de $ o (n^{100}) $ y $ mathrm {dtime dtime } (n^{1000}) $ es la clase de todos los idiomas que puede decidir mediante una máquina de turbación determinista en tiempo polinomial de $ o (n^{1000}) $.

¿Alguna ayuda/sugerencia?

Answer 1

Aquí está la solución usando el relleno. Suponga $ l in mathrm {ntime} (n^{1000}) $. Defina un nuevo lenguaje $ l '= {x0^{| x |^{10}-| x |}: x in l } $. Cada $ x en l $ corresponde a unos $ y en l '$ de longitud $ | y | = | x | + (| x |^{10}-| x |) = | x |^{10} $. Por lo tanto, podemos decidir si $ y en l '$ en tiempo no determinista $ | x |^{1000} = | y |^{100} $, es decir, $ l' en mathrm {ntime} (n^{ 100}) subseteq mathrm {dtime} (n^{1000}) $. Para decidir si $ x en l $, forma $ y = x0^{x^{10}-| x |} $ y ejecute $ | y |^{1000} = | x |^{10000} $ -Algoritmo determinista de tiempo por $ L '$. Concluimos que $ l en mathrm {dtime} (n^{10000}) $.

Answer 2

Divide el problema en dos partes:

1. Hay un $ mathsf {np} $-lenguaje completo en $ mathsf {ntime} (n^{1000}) $.
2. Si un lenguaje completo está en $ mathsf {dtime} (n^{1000}) subset mathsf {p} $ entonces $ mathsf {p} = mathsf {np} $.

Answer 3

Esta es una consecuencia casi trivial de la definición de completidad de NP. Si algún idioma en NP se puede resolver en el tiempo polinomial (que la premisa afirma), entonces todos lo son. Otra forma de ver esto es mirar Teorema de Cook para NP-Completitud Eso reduce todos los idiomas completos de NP al reconocimiento de un lenguaje que involucra SAT y la conversión de la máquina de turación no determinista en SAT.