5
$\begingroup$

$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?

$\endgroup$
6
  • 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, 2015 at 20:31
  • 1
    $\begingroup$ Well, $k=0$ seems like an easy place to start... $\endgroup$ Nov 5, 2015 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, 2015 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$ Nov 5, 2015 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, 2015 at 0:31

1 Answer 1

9
$\begingroup$

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.

$\endgroup$

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.