Content deleted Content added
No edit summary |
m Fixed a tiny grammatical issue in the last sentence |
||
Line 3:
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 (complexity)|NC{{sup|1}}]].<ref>{{cite web|last=Buss|first=Samuel R.|author-link=Samuel Buss|title=The Boolean formula value problem is in ALOGTIME|url=http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean/|website=www.math.ucsd.edu|date=January 1987|accessdate=May 5, 2017}}</ref>
The problem is closely related to the [[Boolean satisfiability problem|Boolean Satisfiability Problem]] which is complete for [[NP (complexity)|NP]] and its complement, the [[Tautology (logic)|Propositional Tautologihood Problem]], which is complete for [[co-NP]].
==References==
| |||