Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

Question

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?

Answer 1

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})$.

Answer 2

Break the problem into two parts:

1. There is a $\mathsf{NP}$-complete language in $\mathsf{NTime}(n^{1000})$.
2. If an $\mathsf{NP}$-complete language is in $\mathsf{DTime}(n^{1000}) \subset \mathsf{P}$ then $\mathsf{P}=\mathsf{NP}$.

Answer 3

This is a near trivial consequence of the definition of NP-completeness. If any language in NP is solvable in polynomial time (which is asserted by the premise), then they all are. Another way to look at this is to look at Cook's theorem for NP-completeness that reduces all NP-complete languages to the recognition of a language involving SAT and the conversion of the nondeterministic Turing machine into SAT.