# Can we show that non-determinism adds no power, for some specific running time?

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

• 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.) – Raphael Nov 5 '15 at 20:31
• Well, $k=0$ seems like an easy place to start... – Eric Towers Nov 5 '15 at 20:59
• @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. – pushkin Nov 5 '15 at 21:07
• See this prior answer, which is essentially a duplicate of the current Question, ( cstheory.stackexchange.com/questions/1079 ) for $k=1$. – Eric Towers Nov 5 '15 at 21:10
• 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. – 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)})$.