[Solved]: Can we show that non-determinism adds no power, for some specific running time?

Problem Detail: 

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

Asked By : pushkin

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49109