Circuit value problem: Difference between revisions

Revision as of 17:12, 24 October 2022

Revision as of 08:01, 5 May 2023

Line 4:

The problem is complete for [[P (complexity)|P]] under uniform [[AC0|AC{{sup|0}}]] reductions. Note that, in terms of [[time complexity]], it can be solved in [[linear time]] simply by a [[topological sort]].

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 webconference |last url=Busshttps://dl.acm.org/doi/pdf/10.1145/28395.28409 |first author=Samuel R. Buss | author-link=Samuel Buss | title=The Boolean formula value problem is in ALOGTIME |url editor=Alfred V. Aho | editor-link=Alfred Aho| book-title=Proceedings of the 19th Annual ACM [[Symposium on Theory of Computing]] (STOC) | publisher=ACM | pages=123&ndash;131 | date=Jan 1987 }} ([http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean/|website=www.math.ucsd.edu|date=January 1987|accessdate=MayAuthor's 5, 2017}}draft])</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 Tautology Problem]], which is complete for [[co-NP]].