5
$\begingroup$

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

Improve this question
$\endgroup$
  • 2
    $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W.♦ Jul 7 '17 at 22:16
4
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Covvar Jul 7 '17 at 19:18
  • 1
    $\begingroup$ You are missing here that you are only outputting the circuit, that is, which gates are connected to which gates, rather than the values computed by the gates. $\endgroup$ – Yuval Filmus Jul 7 '17 at 19:19
  • $\begingroup$ Oh of course (it's only the reduction we're talking about) - Got it. Thanks! $\endgroup$ – Covvar Jul 7 '17 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.