Problem Detail: I’d really like your help with proving the following. If $mathrm{NTime}(n^{100}) subseteq mathrm{DTime}(n^{1000})$ then $mathrm{P}=mathrm{NP}$. Here, $mathrm{NTime}(n^{100})$ is the class of all languages which can be decided by nondeterministic Turing machine in polynomial time of $O(n^{100})$ and $mathrm{DTime}(n^{1000})$ is the class of all languages which can be decided by a deterministic Turing machine in polynomial time of $O(n^{1000})$. Any help/suggestions?
Asked By : Joni
Answered By : Yuval Filmus
Here is the solution using padding. Suppose $L in mathrm{NTime}(n^{1000})$. Define a new language $L’ = {x0^{|x|^{10}-|x|} : x in L}$. Each $x in L$ corresponds to some $y in L’$ of length $|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$. Therefore we can decide whether $y in L’$ in non-deterministic time $|x|^{1000} = |y|^{100}$, i.e. $L’ in mathrm{NTime}(n^{100}) subseteq mathrm{DTime}(n^{1000})$. In order to decide whether $x in L$, form $y = x0^{x^{10}-|x|}$ and run the $|y|^{1000} = |x|^{10000}$-time deterministic algorithm for $L’$. We conclude that $L in mathrm{DTime}(n^{10000})$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6695 Ask a Question Download Related Notes/Documents
