Circuit value problem: Difference between revisions

Revision as of 17:36, 7 April 2017

Revision as of 21:14, 5 May 2017

Line 1:

The '''Circuit Value Problem''' (aka. theor Circuit Evaluation Problem) is the computational problem of computing the output of a given [[Boolean circuit]] on a given input.

is the computational problem of computing the output of a given [[Boolean circuit]] on a given input.

The problem is complete for [[P (complexity)|P]] under uniform [[AC0|AC{{sup|0}}]] 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 [[NC_NC (complexity) | NC1NC{{sup|1}}]].<ref>{{cite web|last1last=Buss|first=Samuel R.|first1author-link=Samuel Buss|title=The Boolean formula value problem (BFVP)is in Alogtime ALOGTIME|url=http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean/|website=www.math.ucsd.edu|date=January 1987|accessdate=3May April5, 20162017}}</ref>

The problem is complete for [[P_(complexity) | 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 [[NC_(complexity) | NC1]]<ref>{{cite web|last1=Samuel|first1=Buss|title=Boolean formula value problem (BFVP) in Alogtime |url=http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean/|website=www.math.ucsd.edu|accessdate=3 April 2016}}</ref>

The problem is closely related to the [[Boolean satisfiability problem | Boolean Satisfiability Problem]] which is complete for [[NP_NP (complexity) | NP]] and its complement [[Tautology_Tautology (logic) | Propositional Tautologihood Problem]] which is complete for [[Coco-NP | coNP]].

{{compu-prog-stub}}