Circuit Value Problem

Computational problem From Wikipedia, the free encyclopedia

Circuit Value 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.

Thumb
Boolean example circuit

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

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.