Revision as of 22:18, 11 October 2016 edit Rathfelder (talk \| contribs) Extended confirmed users 548,785 edits removed Category:Complexity theory using HotCat ← Previous edit		Revision as of 17:36, 7 April 2017 edit undo Arthurb (talk \| contribs) 13 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 [[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 [[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