Why does the circuit value problem run in log space on an alternating Turing machine? It is claimed to be so in my university's lecture notes. Also, it is claimed that monotone circuit value problem has the same space complexity on an alternating Turing machine.

I think it requires at least linear space because it needs to store the current assignment that we are checking and also some bits for the working and storing outputs of sub circuits.


It is a classical result that ALOGTIME=P. You can find a proof in lecture notes of Madhu Sudan. Both the circuit value problem and the monotone circuit value problem are P-complete, and in particular in P, and so can be solved in alternating logarithmic space.

One thing which might be confusing you is that we only measure space on work tapes. Space on the input tape is for free, though this comes at a price: you are not allowed to modify it.

| cite | improve this answer | |
  • $\begingroup$ is there an algorithm to see this? I think the work space still needs to store some assignment for all variable. $\endgroup$ – e_noether Apr 2 '18 at 20:55
  • $\begingroup$ The algorithm is described in the lecture notes. $\endgroup$ – Yuval Filmus Apr 2 '18 at 21:38
  • 1
    $\begingroup$ The truth assignment is available on the input tape. Are you confusing the circuit evaluation problem with SAT? $\endgroup$ – Yuval Filmus Apr 2 '18 at 21:39

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.