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$ – Thinh D. Nguyen Aug 21 '19 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$ – Thinh D. Nguyen Aug 21 '19 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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