Jump to content

Circuit value problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dyadron (talk | contribs) at 21:14, 5 May 2017 (Samuel Buss' given name/surname mismatched; exact title of Buss' paper; Wikifying). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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. 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 Propositional Tautologihood Problem which is complete for co-NP.

Stub icon

This computer-programming-related article is a stub. You can help Wikipedia by expanding it.

References

  1. ^ Buss, Samuel R. (January 1987). "The Boolean formula value problem is in ALOGTIME". www.math.ucsd.edu. Retrieved May 5, 2017.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Circuit_value_problem&oldid=778900937"