Circuit Value Problem

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

  1. ↑ Samuel, Buss. "Boolean formula value problem (BFVP) in Alogtime". www.math.ucsd.edu. Retrieved 3 April 2016.
This article is issued from Wikipedia - version of the 10/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.