$NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$

$P = \cup_{k \in \mathbb{N}} TIME(n^k)$

Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$?

For how large of a $k$ can we show the above statement to be true?

  • 4
    $\begingroup$ What have you tried and where did you get stuck? (Come on people, how did this get six upvotes? It's a problem dump like any other.) $\endgroup$ – Raphael Nov 5 '15 at 20:31
  • 1
    $\begingroup$ Well, $k=0$ seems like an easy place to start... $\endgroup$ – Eric Towers Nov 5 '15 at 20:59
  • $\begingroup$ @Raphael I just learned about this today. This is not part of a homework problem (if that's what you mean by "problem dump"). I barely have the mathematical background at this point to solve this - I was just curious. $\endgroup$ – pushkin Nov 5 '15 at 21:07
  • 3
    $\begingroup$ See this prior answer, which is essentially a duplicate of the current Question, ( cstheory.stackexchange.com/questions/1079 ) for $k=1$. $\endgroup$ – Eric Towers Nov 5 '15 at 21:10
  • 4
    $\begingroup$ Our policy generally doesn't depend on whether it was assigned to you as a homework. "Problem dump" means that the question provides only the statement of a problem, without showing anything about what you've tried or where you got stuck and without formulating a specific question about some aspect of the problem. Such questions are often discouraged, for reasons explained here. It's often better to make a serious attempt before asking, and show us what approaches you tried. $\endgroup$ – D.W. Nov 6 '15 at 0:31

If $\mathsf{NTIME}(n^k) \subseteq \mathsf{TIME}(n^\ell)$ for any $k,\ell$ then $\mathsf{P} = \mathsf{NP}$. Indeed, any problem $L \in \mathsf{NP}$ can be solved in non-deterministic time $O(n^r)$ for some $r$. Consider now the problem $L' = \{0^{|x|^{r/k}}1x : x \in L\}$. Clearly this problem is still in $\mathsf{NP}$, and furthermore the previous algorithm solves it in non-deterministic time $O(n^k)$. Therefore $L'$ has a deterministic algorithm running in time $O(n^\ell)$, implying that $L$ has a deterministic algorithm running in time $O(n^{r(\ell/k)})$.

This trick is known as padding.

| cite | improve this answer | |

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.