Can nondeterminism speed-up deterministic computation? If yes, how much?By speeding-up deterministic computation by nondeterminism I mean results of the form:$\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n)$E.g. something like$\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n)$What is the best known speed-up result of deterministic computation by nondeterminism?What about $\mathsf{\Sigma^P_kTime}(n)$ or even $\mathsf{ATime}(n)$ in place of $\mathsf{NTime}(n)$?Assume that complexity classes are defined using multiple-tape Turing machines to avoid the well-know peculiarities of the sub-quadratic time single-tape Turing machines.
Nondeterministic speed-up of deterministic computation
cc.complexity theory;nondeterminism;speed up;alternation;tradeoff
You should not expect an exciting speed-up. We have$$\mathrm{DTIME}(f(n))\subseteq\mathrm{NTIME}(f(n))\subseteq\mathrm{ATIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)),$$and the best known simulation of deterministic time by space is still the HopcroftPaulValiant theorem$$\mathrm{DTIME}(f(n))\subseteq\mathrm{DSPACE}(f(n)/\log f(n)).$$Thus, nondeterminism or alternation is not known to give speed-up by more than a logarithmic factor. (I suspect no super-linear speed-up is known either, though Im not sure if the HPV theorem cant be made to work with ATIME in place of DSPACE.)