# The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6)

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

Suppose that $$\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$$. Then $$\Sigma_2$$-$$\mathsf{TIME}(n^{8}) \subseteq \mathsf{NTIME}(n^{9.6})$$,

which they prove in the following way:

• If $$L \in \Sigma_2$$-$$\mathsf{TIME}(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 $$\mathsf{NTIME}(n) \subseteq \mathsf{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. Aug 21, 2019 at 3:49
• Then $D$ will play the role of a de-quantifier machine that peels off the $\forall v$ quantifier for you. Aug 21, 2019 at 3:55
• @ThinhD.Nguyen I believe it should imply $DTIME(n^{9.6}) \supseteq coNTIME(n^8)$. Nov 7, 2020 at 20:20

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.