I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book.

Please give a semi-detailed proof of this. I have found a paper which has this proof(by Chandra, Kozen et al.) but found it too hard to understand.


I Asked this once and my post was closed. I remember saying i have no idea, and i'm in need of some enlightenment. Eventually i found the solution somewhere and i think that my problem was that i was not as comfortable as i thought with the ideas appearing in the proof of the Cook-Levin theorem.

The interesting direction is $EXP\subseteq APSPACE$. Let $L\in EXP$ be some language decidable in $2^{n^c}$ time, i.e. there exists a Turing machine $M_L$ which runs in $2^{n^c}$ time deciding $L$.

For any input $x$, we can look at the $2^{|x|^c}\times 2^{|x|^c}$ computation table of $M_L$ on x. The i'th row describes the $i'th$ configuration during the computation: $\sigma_1\sigma_2...\sigma_i q\sigma_{i+1}...\sigma_{2^{|x|^c}}$, where $\sigma_i\in \Sigma\cup \Gamma, q\in Q$. This means that at the $i'th$ step $\sigma_1...\sigma_{2^{|x|^c}}$ is the content of the working tape, we are at state $q$, and the head is at the symbol appearing after $q$ (we should also include the input somewhere, but specifics don't really matter here).

We denote by $C_{ij}$ the content of the cell in the $i'th$ row and $j'th$ column in the computation table of $M_L(x)$.

Our APSPACE machine will be able to decide whether or not $C_{ij}=\sigma$ (then you can go over the last row and check if $q_{acc}$ is written somewhere). Note that the index $i$ can be written in polynomial number of bits.

As in the Cook-Levin theorem, the important fact is that computation is local. The value of $C_{ij}$ is determined by the values $C_{i-1,j-1},C_{i-1,j},C_{i-1,j+1},C_{i-1,j+2}$, say by some known function $g$ ($g$ of course depends on the transition function of $M_L$), meaning:

$\forall \sigma\in\Sigma\cup \Gamma\cup Q: \hspace{1mm} C_{ij}=\sigma \iff \exists \sigma_1,\sigma_2,\sigma_3,\sigma_4: \hspace{1mm} C_{i-1,j-1}=\sigma_1 \land C_{i-1,j}=\sigma_2\land C_{i-1,j+1}=\sigma_3 \land C_{i-1,j+2}=\sigma_4 \land \sigma = g\left(\sigma_1,\sigma_2,\sigma_3,\sigma_4\right).$

To decide whether $C_{ij}=\sigma$, under existential quantifiers, nondeterministically guess $\sigma_1,\sigma_2,\sigma_3,\sigma_4$. Verify that $\sigma = g\left(\sigma_1,\sigma_2,\sigma_3,\sigma_4\right)$, if not reject.

The next step is to verify recursively that $C_{i-1,j-1}=\sigma_1 \land C_{i-1,j}=\sigma_2\land C_{i-1,j+1}=\sigma_3 \land C_{i-1,j+2}=\sigma_4$. Let us denote by $S_i$ the space used by our machine, when it begins with the i'th configuration (i.e. verifying $C_{ij}=\sigma$ for some $j,\sigma$). Even if we use the same space for all four calls, you get $S_i=S_{i-1}+poly(|x|)=...=2^{|x|^c}poly(|x|)$. This happens because we keep a call stack (we dont overwrite the current frame), to overcome this:

under universal quantifiers, write nondeterministically $\left(J,\sigma_J\right)\in \left\{\left(j-1,\sigma_1 \right),\left(j,\sigma_2 \right),\left(j+1,\sigma_3 \right),\left(j+2,\sigma_4 \right)\right\}$ (suppose for simplicity that your machine has four transition functions), and output "yes" if $C_{i-1,J}=\sigma_J$.

The universal quantifiers allowed us to compute the conjunction of four recursive calls simultaneously, thus we dont need to keep a call stack. In that case, in all times we need only remember $i,j,\sigma$, which requires polynomial space (in the recursive call for $C_{i-1,J}$, we use the same space that was used to store $i$).

  • $\begingroup$ I am having trouble wrapping my mind around the computation table, since it is exponential in time it can also be in size. How do we represent the table? Is the answer: "Given the input to the EXPTIME-Problem and the final state of the TM, we can reconstruct the computation using the transition function?" $\endgroup$ – isset Aug 10 '17 at 7:02

The proof is very similar to the proof that ALOGSPACE=P, given for example in these lecture notes (in fact, you can probably derive APSPACE=EXP from ALOGSPACE=P by padding). For your convenience, here are the main ideas.

APSPACE$\subseteq$EXP: Consider some machine operating in alternating space $s$. The machine has $2^s$ configurations, and we can ensure that no run involves a repeated configuration. Construct a circuit which corresponds to this computation. The vertices are the individual configurations, and these are annotated by AND or OR according to the player in charge (its a DAG since no configuration repeats). This circuit has exponential size and so can be evaluated in EXP.

EXP$\subseteq$APSPACE: Consider some machine operating in exponential time. Represent its computation as a uniform circuit of exponential size. Note that the name of a node takes up only polynomial space. Convert the circuit into an alternating machine in the natural way. This machine only needs space to store one or two nodes.


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.