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$?

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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.