[Solved]: Proof of APSPACE = EXP

Problem Detail: 

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.

Asked By : ma08

Answered By : Ariel

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$).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49639

3.2K people like this

 Download Related Notes/Documents