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.