patternMinor
Does the circuit value problem require only log space in alternating Turing machines
Viewed 0 times
problemthespacelogvaluedoesrequireturingmachinesonly
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#90127, answer score: 3
Revisions (0)
No revisions yet.