Circuit value problem
Jump to navigation
Jump to search
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 with respect to AC0 reductions.[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
[edit | edit source]References
[edit | edit source]- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value). (Author's draft)
- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
