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
