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?

  • 7
    $\begingroup$ Hint: padding. $\endgroup$
    – sdcvvc
    Commented Nov 16, 2012 at 14:55
  • $\begingroup$ where does this question originate from? $\endgroup$
    – vzn
    Commented Nov 16, 2012 at 21:55

3 Answers 3


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


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

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.

  • 3
    $\begingroup$ What you said is true, but of NP complete languages (not NP languages). We also need to show that there exists an NP complete language solvable in $NTime(n^{100})$-true, I think, but not obvious by definition. $\endgroup$
    – SamM
    Commented Nov 16, 2012 at 17:45
  • $\begingroup$ agreed, good pt. think this follows from bounds in the Cook proof....? all NP machines can be converted/solved by SAT in NTime($n^c)$, $c<100$...? $\endgroup$
    – vzn
    Commented Nov 16, 2012 at 18:39
  • 3
    $\begingroup$ @vzn: I don't think we can prove $c \lt 100$. I believe you might be contradicting one of the hierarchy theorems... $\endgroup$
    – Aryabhata
    Commented Nov 16, 2012 at 21:33
  • $\begingroup$ after thinking about it a little more carefully, agree. (initial glance, thought this was a basic question...) cooks proof creates a new SAT that is polynomially bounded in size relative to the original machine but the initial machine is unbounded in the polynomial exponent (wrt that proof). if I derived a contradiction then $P \neq NP$ =) ... anyway maybe we are saying this is actually an open question? ie not known to be either true or false wrt existing theory? $\endgroup$
    – vzn
    Commented Nov 16, 2012 at 21:51
  • 4
    $\begingroup$ @vzn: The question can be solved using the technique of padding, alluded to by sdcvvc. $\endgroup$ Commented Nov 16, 2012 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.