Circuit Value Problem
Boolean example circuit
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 (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.
References[]
- ^ Buss, Samuel R. (January 1987). "The Boolean formula value problem is in ALOGTIME". www.math.ucsd.edu. Retrieved May 5, 2017.
 | This computer-programming-related article is a stub. You can help Wikipedia by . |
Categories:
- Polynomial-time problems
- Computational problems
- Theoretical computer science
- Computer programming stubs