# Why is CVAL a P-Complete problem?

We've learned in class that CVAL is P-complete. CVAL is the language of all $\langle C,x\rangle$ where $C$ is a formula (a circuit which outputs $0$ or $1$) and $x$ is some input for $C$ such that $C(x) = 1$.

We've done this in the same fashion Michael Sipser does in this paper (accessed Jul 11, 2017).

The reduction itself is pretty much clear. What isn't clear to me is why we can make this reduction in $\mathcal O (\log n)$ space?

It's clear that every cell is dependent on some constant number of cells of the above row (= previous configuration). Yet, one would end up calculating recursively more and more cells, until reaching the very first configuration.

We did learn in class how to evaluate $f_2 (f_1(x))$ effectively, with $\log n$ space - You start with computing $f_2$, and when in need, you "ask" $f_1$ for some symbol. I don't see how to apply it in our case.

• How? The output tape is write-only, so I can't read the last row I just wrote and obviously my working tape isn't sufficient to remember $n^k$ cells (it has a $\log(n)$-space bound). What am I missing then? – Covvar Jul 7 '17 at 19:18