1
$\begingroup$

I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505)

20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ will be called a leaf language. Let A and R be two disjoint leaf languages (the accepting and rejecting leaf language, respectively). Now, any two such languages define a complexity class: Let C[A, R] be the class of all languages L such that there is a (standardized) nondeterministic Turing machine N with the following property: $x \in L$ if and only if $N (x) \in A,$ and $x \notin L$ if and only if $N(x) \in R.$ ... Show that, if $A, R \in NL,$ then $C[A, R] \subseteq PSPACE.$

How does one show this? I thought there'd be a way to use the result $AP = PSPACE$ directly but I can't see how.

$\endgroup$

1 Answer 1

1
$\begingroup$

You are omitting some very important details. In the exercise, the Turing machine $N$ is required to halt on all its possible computation paths using exactly $p(n)$ steps, where $n$ is the size of the input, and $p(n)$ is upper bounded by a polynomial. Moreover, each non-deterministic choice is labelled as either $0$ or $1$, which induces an order on the computation paths and hence on the leaves of the computation tree (the $\ell$-th computation path corresponds to the non-deterministic choices given by the binary representation of $\ell$). Each of the leaves is also labelled with either $0$ or $1$ (e.g., for reject/accept). The output $N(x)$ of the execution of $N$ on $x$ is the binary string in $\{0,1\}^{p(n)}$ that corresponds the labels of the leaves, in the order discussed above.

Now we can actually tackle the exercise. Since $A$ and $R$ are in $NL$, there must be some non-determistic Turing machines $T_A, T_B$ that decide $A$ and $B$, respectively, and use space $O(\log n)$.

Given a language $L \in C[A,R]$, we can show that $L \in \mathsf{PSPACE}$ by providing a Turing machine $T^*$ that takes an input $x$ and decides whether $x \in L$ using at most polynomial amount of space.

The Turing machine $T^*$ first computes the number of steps $p(|x|)$ taken by $N(x)$ (we can simply simulate one computation path of $N(x)$). Then $T^*$ simulates two parallel execution of $T_A$ and $T_B$ on the string $y=N(x)$. Since we cannot explicitly generate $y$ (which has length $2^{p(n)}$), we also "simulate" the views that $T_A$ and $T_B$ have over the contents of their tape. Whenever $T_A$ or $T_B$ want to write to a location $\ell$ of their simulated tape, we store the index $\ell$ and the written symbol (possibly replacing the previous symbol stored in $\ell$) in the tape of $T^*$. Whenever $T_A$ or $T_B$ want to read a location $\ell$ of their simulated tape, we first check if $\ell$ was previously written to. If that's the case we answer with the symbol we previously stored. If $\ell$ was never written to, then either we return the blank tape symbol (if $\ell > 2^{p(n)}$) or we return the $\ell$-th symbol of $y$ (when $\ell \le 2^{p(n)}$). To compute the $\ell$-th symbol of $y$ we can simply simulate the $\ell$-th computaton path of $N(x)$.

Notice that the size of the (simulated) input to the simulated versions of $T_A$ and $T_B$ is $|y| = 2^{p(n)}$ yet, since $T_A$ and $T_B$ use logarithmic space, there are at most $O(\log 2^{p(n)}) = O(p(n))$ distinct locations that are written to (which $T^*$ needs to keep track of).

Eventually, one of $T_A(N(x))$ and $T_B(N(x))$ must accept. In the former case $T^*$ also accepts, while in the latter case $T^*$ rejects.

$\endgroup$

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.