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 $EXPsubseteq APSPACE$. Let $Lin 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_1sigma_2…sigma_i qsigma_{i+1}…sigma_{2^{|x|^c}}$, where $sigma_iin Sigmacup Gamma, qin 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 sigmainSigmacup Gammacup 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_2land C_{i-1,j+1}=sigma_3 land C_{i-1,j+2}=sigma_4 land sigma = gleft(sigma_1,sigma_2,sigma_3,sigma_4right).$ To decide whether $C_{ij}=sigma$, under existential quantifiers, nondeterministically guess $sigma_1,sigma_2,sigma_3,sigma_4$. Verify that $sigma = gleft(sigma_1,sigma_2,sigma_3,sigma_4right)$, if not reject. The next step is to verify recursively that $C_{i-1,j-1}=sigma_1 land C_{i-1,j}=sigma_2land 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_Jright)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
