Circuit value problem: Difference between revisions

Revision as of 19:36, 22 July 2017

Latest revision as of 13:32, 19 June 2025

(15 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|Computational problem}}

The '''Circuit Value Problem''' (or Circuit Evaluation Problem) is the computational problem of computing the output of a given [[Boolean circuit]] on a given input.

[[File:Combinatorial Logic Example.svg|thumb|An example Boolean circuit]]

The '''Circuitcircuit Valuevalue Problemproblem''' (or Circuitcircuit Evaluationevaluation Problemproblem) is the computational problem of computing the output of a given [[Boolean circuit]] on a given input.

The problem is complete for [[P (complexity)|P]] under uniform [[AC0|AC{{sup|0}}]] reductions. TheNote [[Booleanthat, Formulain Valueterms Problem]] (orof [[Booleantime Formula Evaluation Problemcomplexity]]), isit thecan specialbe casesolved ofin the[[linear problemtime]] whensimply the circuit isby a tree. The Boolean Formula Value Problem is complete for [[NCtopological (complexity)|NC{{sup|1}}sort]].<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 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&ndash;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|Boolean Satisfiability Problem]] which is complete for [[NP (complexity)|NP]] and its complement [[Tautology (logic)|Propositional Tautologihood Problem]] which is complete for [[co-NP]].

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)|Propositionalpropositional Tautologihoodtautology Problemproblem]], which is complete for [[co-NP]].

== See also ==

* [[Circuit satisfiability]]

* [[Switching lemma]]

==References==

{{Reflist}}

* {{cite journal | url= | doi=10.1145/990518.990519 | author=Richard E. Ladner | author-link=Richard E. Ladner | title=The circuit value problem is log space complete for P | journal=[[ACM SIGACT News]] | volume=7 | number=101 | pages=18&ndash;20 | date=Jan 1975 }}

[[Category:Polynomial-time problems]]