Provando que, se

Eu realmente gostaria da sua ajuda para provar o seguinte.

Se então .P = N $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$$\mathrm{P}=\mathrm{NP}$

Aqui, é a classe de todas as línguas que podem ser decididas pela máquina de Turing não determinística no tempo polinomial de e é a classe de todas as línguas que pode ser decidida por uma máquina de Turing determinística no tempo polinomial de .O ( n 100 ) D T i m e ( n 1000 ) O ( n 1000$\mathrm{NTime}(n^{100})$$O(n^{100})$$\mathrm{DTime}(n^{1000})$$O(n^{1000})$

Alguma ajuda / sugestões?

Aqui está a solução usando preenchimento. Suponha . Definir um novo idioma L ′ = { x 0 | x | 10 - | x | : x ∈ L } . Cada x ∈ L corresponde a algum y ∈ L ′ de comprimento | y | = | x | + ( |$L \in \mathrm{NTime}(n^{1000})$$L' = \{x0^{|x|^{10}-|x|} : x \in L\}$$x \in L$$y \in L'$ . Portanto, podemos decidir sey∈ L ′ em tempo não determinístico | x | 1000 = | y | 100 , ou seja, G ' ∈ N t i m e ( n 100 )⊆ D t i m e ( n 1000 ). Para decidir sex$|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})$ , forma y = x 0 x 10 - | x | e execute o | y | 1000 = | x | Algoritmo determinístico de 10000 tempos para L ′ . Concluímos que L ∈ D T i m e ( n 10000 ) .$x \in L$$y = x0^{x^{10}-|x|}$$|y|^{1000} = |x|^{10000}$$L'$$L \in \mathrm{DTime}(n^{10000})$

Divida o problema em duas partes:

1. Existe um idioma completo em N T i m e ( n 1000 ) .$\mathsf{NP}$$\mathsf{NTime}(n^{1000})$
2. Se um língua -completo é em D t i m e ( n 1000 ) ⊂ P então P = N P .$\mathsf{NP}$$\mathsf{DTime}(n^{1000}) \subset \mathsf{P}$$\mathsf{P}=\mathsf{NP}$

Esta é uma conseqüência quase trivial da definição de NP-completude. Se qualquer linguagem em NP é solucionável em tempo polinomial (o que é afirmado pela premissa), então todas são. Outra maneira de analisar isso é analisar o teorema de Cook para a completude do NP, que reduz todas as linguagens completas ao NP ao reconhecimento de uma linguagem que envolve o SAT e a conversão da máquina de Turing não determinística em SAT.