Revision as of 22:16, 3 April 2016 edit RDT (talk \| contribs) 295 edits Initial article.		Revision as of 22:18, 3 April 2016 edit undo RDT (talk \| contribs) 295 edits No edit summary Next edit →
Line 4: 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 [[NC1]]<ref>{{cite web\|last1=Samuel\|first1=Buss\|title=Boolean formula value problem (BFVP) in Alogtime\|url=www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean/\|website=www.math.ucsd.edu\|accessdate=3 April 2016}}</ref> ~~the special case of the problem when the circuit is a tree.~~ The problem is closely related to [[Boolean satisfiability problem \| Boolean Satisfiability Problem]] which is complete for [[NP_(complexity) \| NP]] and its complement [[Tautology_(logic) \| Propositional Tautologihood Problem]] which is complete for [[Co-NP \| coNP]].

Circuit value problem: Difference between revisions