Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
7  
Hint: padding. –  sdcvvc Nov 16 '12 at 14:55
    
where does this question originate from? –  vzn Nov 16 '12 at 21:55

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer

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}$.
share|improve this answer

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.

share|improve this answer
3  
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. –  SamM Nov 16 '12 at 17:45
    
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$...? –  vzn Nov 16 '12 at 18:39
3  
@vzn: I don't think we can prove $c \lt 100$. I believe you might be contradicting one of the hierarchy theorems... –  Aryabhata Nov 16 '12 at 21:33
    
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? –  vzn Nov 16 '12 at 21:51
4  
@vzn: The question can be solved using the technique of padding, alluded to by sdcvvc. –  Yuval Filmus Nov 16 '12 at 22:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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