Prouver que si $ \ mathrm {} NTIME (n ^ {100}) \ subseteq \ mathrm {} dTime (n ^ {1000}) $, alors $ \ mathrm {P} = \ mathrm {NP} $

Question

Je voudrais vraiment votre aide prouver ce qui suit.

Si $ \ mathrm {NTIME} (n ^ {100}) \ subseteq \ mathrm {dTime} (n ^ {1000}) $, alors $ \ mathrm {P} = \ mathrm {NP} $.

Ici, $ \ mathrm {NTIME} (n ^ {100}) $ est la classe de toutes les langues qui peut être décidé par une machine non déterministe de Turing en temps polynomiale de O $ (n ^ {100}) $ et $ \ mathrm {} dTime (n ^ {1000}) $ est la classe de toutes les langues qui peuvent être décidées par une machine de Turing déterministe en temps polynomiale de O $ (n ^ {1000}) $.

Toute aide / suggestions?

Answer 1

Voici la solution en utilisant un rembourrage. Supposons $ L \ in \ mathrm {} NTIME (n ^ {1000}) $. Définir une nouvelle langue $ L »= \ {X0 ^ {| x | ^ {10} - | x |}: x \ in L \} $. Chaque $ x \ in L correspond de $ à quelque $ y \ à L '$ de longueur $ | y | = | X | + (| X | ^ {10} - | x |) = | x | ^ {10} $. Nous pouvons donc décider si $ y \ à L '$ dans le temps non déterministe $ | x | ^ {1000} = | y | ^ {100} $, soit $ L \' en \ mathrm {NTIME} (n ^ { 100}) \ subseteq \ mathrm {} dTime (n ^ {1000}) $. Afin de décider si $ x \ in L $, forme $ y = x0 ^ {x ^ {10} - | x |} $ et exécuter le $ | y | ^ {1000} = | x | ^ {10000} $ algorithme déterministe -temps pour $ L '$. Nous concluons que $ L \ in \ mathrm {} dTime (n ^ {10000}) $.

Answer 2

Briser le problème en deux parties:

1. Il y a un $ \ mathsf {NP} $ -. Langage complet en $ \ mathsf {} NTIME (n ^ {1000}) $
2. Si un $ \ mathsf {NP} $ - langage complet est en $ \ mathsf {dTime} (n ^ {1000}) \ subset \ mathsf {P} $, alors $ \ mathsf {P} = \ mathsf {NP } $.

Answer 3

Ceci est une conséquence triviale proche de la définition du NP-complet. Si une langue NP est résoluble en temps polynomial (qui est affirmé par la prémisse), puis ils sont tous. Une autre façon de voir cela est de regarder Faire cuire NP-complet qui réduit toutes les langues NP-complets à la reconnaissance d'une langue impliquant SAT et la conversion de la machine de Turing non déterministes en SAT.