0
$\begingroup$

Assume $NTime(2^n)\subseteq DTime(n^n)$, what can you conclude about $DSpace(n^n)$?

I don't know if this is the correct approach, but here was my attempt at an answer:

Let $A \in DSpace(n^n) $ and define language $B= \{ <x,0^{log(|x|^{|x|}) - |x|}> : x \in A \} $. Define a machine $M_B$ that receives input $y$, checks it's of the form $y= <x, 0^{log(|x|^{|x|}) - |x|}> $, and if so simulates the $DSpace(n^n)$ machine on $x$. Then $M_B$ decides B in $DSpace(|x|^{|x|})=DSpace(2^{|y|})$, and so by assumption there exists a machine $M'_B$ that decides $B$ in $DTime(n^n)$.

Now we can define a machine $M'_A$ that receives input $x$, builds $y= <x,0^{log(|x|^{|x|}) - |x|}> $, and calls $M'_B$. Then for input length $n$, $M'_B$ runs in time $O(log(n^n))+O((n \cdot log(n))^{n \cdot log(n)}) = O((n \cdot log(n))^{n \cdot log(n)})$. Since $n \cdot log(n) = O(n^2)$, we can say that $M'_B$ runs in $O((n^2)^{n^2})=O(n^{n^2})$. Thus, we can say that $NTime(n^n) \subseteq DTime(n^{n^2}).$

I still have trouble when using the padding argument in various questions (e.g., "if $NTime/NSpace(f) \subseteq DTime/DSpace(g)... $), so I don't know if I made a mistake or if there are stronger claims that can be made.

Also, correct me if I'm wrong, but is it true that if we have $NTime(n) \subseteq DTime(n^c)$ for some constant $c$, then $P=NP$? If so, then does the same conclusion hold if we have $NTime(f(n)) \subseteq DTime(n^c)$ for some function $f(n)>n?$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.