Circuit Value Problem
From HandWiki
Short description: Computational problem
The Circuit Value Problem (or Circuit Evaluation Problem) is the computational problem of computing the output of a given Boolean circuit on a given input.
The problem is complete for P under uniform AC0 reductions. Note that, in terms of time complexity, it can be solved in linear time simply by a topological sort.
The Boolean Formula Value Problem (or Boolean Formula Evaluation Problem) is the special case of the problem when the circuit is a tree. The Boolean Formula Value Problem is complete for NC1.[1]
The problem is closely related to the Boolean Satisfiability Problem which is complete for NP and its complement, the Propositional Tautology Problem, which is complete for co-NP.
See also
- Circuit satisfiability
- Switching lemma
References
- ↑ Samuel R. Buss (Jan 1987). "The Boolean formula value problem is in ALOGTIME". in Alfred V. Aho. ACM. pp. 123–131. https://dl.acm.org/doi/pdf/10.1145/28395.28409. (Author's draft)
- Richard E. Ladner (Jan 1975). "The circuit value problem is log space complete for P". ACM SIGACT News 7 (101): 18–20. doi:10.1145/990518.990519.
 |  |
