Prouver que si alors

J'aimerais vraiment votre aide pour prouver ce qui suit.

Si alors .$\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$$\mathrm{P}=\mathrm{NP}$

Ici, est la classe de toutes les langues qui peut être décidée par la machine de Turing non déterministe en temps polynomial de et est la classe de tous les langages qui peut être décidée par une machine de Turing déterministe en temps polynomial de .$\mathrm{NTime}(n^{100})$$O(n^{100})$$\mathrm{DTime}(n^{1000})$$O(n^{1000})$

Une aide / suggestions?

Voici la solution utilisant le rembourrage. Supposons que . Définissez une nouvelle langue . Chaque correspond à certains de longueur . Nous pouvons donc décider si en temps non déterministe , c'est-à-dire . Afin de décider si , formez et exécutez l' algorithme déterministe de temps pourL ′ = { x 0 | x | 10 - | x | : x ∈ L } x ∈ L y ∈ L ′ | y | = | x | + ( | x | 10 - | x | ) = | x | 10$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}$| x | 1000 = | y | 100 L ′ ∈ N T i m e ( n 100 ) ⊆ D T i m e ( n 1000 ) x ∈ L y = x 0 x 10 - | x | | y | 1000 = | x | 10000 L ′ L $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'$. Nous concluons que .$L \in \mathrm{DTime}(n^{10000})$

Divisez le problème en deux parties:

1. Il existe un langage complet dans .N T i m e ( n 1000$\mathsf{NP}$$\mathsf{NTime}(n^{1000})$
2. Si un langage complet est dans alors .D T i m e ( n 1000 ) ⊂ P P = N $\mathsf{NP}$$\mathsf{DTime}(n^{1000}) \subset \mathsf{P}$$\mathsf{P}=\mathsf{NP}$

Il s'agit d'une conséquence quasi triviale de la définition de la complétude NP. Si un langage en NP est résoluble en temps polynomial (ce qui est affirmé par la prémisse), alors ils le sont tous. Une autre façon de voir les choses est de regarder le théorème de Cook pour l'exhaustivité de NP qui réduit tous les langages NP-complets à la reconnaissance d'un langage impliquant SAT et la conversion de la machine de Turing non déterministe en SAT.