# $NL$ Leaf languages and $PSPACE$

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.

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.