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 Nov 16 '12 at 14:55
  • $\begingroup$ where does this question originate from? $\endgroup$ – vzn Nov 16 '12 at 21:55

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 Nov 16 '12 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 Nov 16 '12 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 Nov 16 '12 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 Nov 16 '12 at 21:51
  • 4
    $\begingroup$ @vzn: The question can be solved using the technique of padding, alluded to by sdcvvc. $\endgroup$ – Yuval Filmus Nov 16 '12 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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