Circuit Value Problem
From Infogalactic: the planetary knowledge core
The Circuit Value Problem (aka. the 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. The Boolean Formula Value Problem (aka. 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 Boolean Satisfiability Problem which is complete for NP and its complement Propositional Tautologihood Problem which is complete for coNP.
References
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
