Content deleted Content added
Adumbrativus (talk | contribs) m Adumbrativus moved page Circuit Value Problem to Circuit value problem without leaving a redirect: Requested by Nyq at WP:RM/TR: names of mathematical problems are common nouns and are not capitalized, however a redirect with decapitalized title already exists, so I can't rename it myself |
m Removed link, typo |
||
| (One intermediate revision by the same user not shown) | |||
Line 5:
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}}]] with respect to AC{{sup|0}} reductions.<ref>{{cite conference | url=https://dl.acm.org/doi/pdf/10.1145/28395.28409 | author=Samuel R. Buss | author-link=Samuel Buss | title=The Boolean formula value problem is in ALOGTIME | 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–131 | date=Jan 1987 | doi=10.1145/28395.28409 | url-access=subscription }} ([http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean Author's draft])</ref>
The problem is closely related to the [[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]].
| |||