# Question about proof of $NTIME(n) \subseteq DTIME(n^{1.2})$ implies $\Sigma_2-TIME(n^{8}) \subseteq NTIME(n^{9.6})$

In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2):

Suppose that $$NTIME(n) \subseteq DTIME(n^{1.2})$$. Then $$\Sigma_2TIME(n^{8}) \subseteq NTIME(n^{9.6})$$

Which they prove in the following way:

• If $$L \in \Sigma_2TIME(n^8)$$, then $$\exists$$ TM M which runs in time $$O(|x|^8)$$ s.t. $$x \in L \leftrightarrow \exists u \in \{0,1\}^{c|x|^8} \forall v \in \{0,1\}^{d|x|^8} M(x,u,v) = 1$$
• But if $$NTIME(n) \subseteq DTIME(n^{1.2})$$, then

by a simple padding argument, we have a deterministic algorithm $$D$$ that on inputs $$x, u$$ with $$|x| = n$$ and $$|u| = cn^8$$ runs in time $$O((n^8)^{1.2}) = O(n^{9.6})$$ and returns $$1$$ iff there exists some $$v \in \{0,1\}^{dn^8}$$ such that $$M(x,u,v) = 0$$

I struggle to see what this "simple padding argument" might be? That is, how do we get respective deterministic algorithm $$D$$ if we have the TM $$M$$?

• Isn't it clear enough that standard padding technique is able to demonstrate that $DTIME(n^{1.2})\supseteq NTIME(n)\implies DTIME(n^{9.6})\supseteq NTIME(n^8)$? Hint: $D$ mimics $M$ by first padding the input length to $n^8$ (with trailing dummy symbols) then enters the start state of $M$ and runs $M$ on the padded input. – Thinh D. Nguyen Aug 21 at 3:49
• Then $D$ will play the role of a de-quantifier machine that peels off the $\forall v$ quantifier for you. – Thinh D. Nguyen Aug 21 at 3:55

The language $$L_1 = \{(x,u) ~|~ \exists v\in \{0,1\}^{d|x|^8}M(x,u,v) = 0\}$$ belongs to $$NTIME(n)$$ by design, since $$|v| = O(|x| + |u|) = O(|x|^{8})$$. By the assumption of the theorem, $$L_1$$ is decidable by some deterministic $$D$$ in $$O((|x|+|u|)^{1.2}) = O(|x|^{9.6})$$ steps. The recipee for $$D$$ isn't important, but the existence of such algorithm $$D$$ leads to the last step of the proof.