Jump to content

Circuit value problem

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by RDT (talk | contribs) at 22:16, 3 April 2016 (Initial article.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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 problem is closely related to Boolean Satisfiability Problem which is complete for NP and its complement Propositional Tautologihood Problem which is complete for coNP.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Circuit_value_problem&oldid=713412906"