patternMinor
Why is CVAL a P-Complete problem?
Viewed 0 times
problemwhycompletecval
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.
I'd be glad for clarificatoins
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.
I'd be glad for clarificatoins
Solution
The reduction doesn't calculate the values of all cells. Rather, it outputs a circuit which calculates (recursively) the values of all cells. You can output the circuit using only logarithmic space, while evaluating it probably requires more space (unless L=P) since CVAL is P-complete.
Context
StackExchange Computer Science Q#77667, answer score: 4
Revisions (0)
No revisions yet.