Circuit value problem: Difference between revisions

Revision as of 18:19, 19 September 2020

Revision as of 16:46, 23 October 2022

Line 7:

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]].

== See also ==

* [[Boolean circuit]]

* [[Circuit satisfiability]]

* [[Switching lemma]]

==References==