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.


1 Answer 1


It is a classical result that ALOGSPACE=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.

  • $\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, 2018 at 20:55
  • $\begingroup$ The algorithm is described in the lecture notes. $\endgroup$ Apr 2, 2018 at 21:38
  • 1
    $\begingroup$ The truth assignment is available on the input tape. Are you confusing the circuit evaluation problem with SAT? $\endgroup$ Apr 2, 2018 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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