Content deleted Content added
m Minor fix |
m Minor fix |
||
Line 2:
In [[theoretical computer science]], the '''circuit satisfiability problem''' (also known as '''CIRCUIT-SAT''', '''CircuitSAT''', '''CSAT''', etc.) is the [[decision problem]] of determining whether a given [[Boolean circuit]] has an assignment of its inputs that makes the output true.<ref name="np-complete-problems">{{cite web|url=http://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf|title=Lecture 7: NP-Complete Problems|date=July 5, 2000|author=David Mix Barrington and Alexis Maciel}}</ref> In other words, it asks whether the inputs to a given Boolean circuit can be consistently set to '''1''' or '''0''' such that the circuit outputs '''1'''. If that is the case, the circuit is called ''satisfiable''. Otherwise, the circuit is called ''unsatisfiable.'' In the figure to the right, the left circuit can be satisfied by setting both inputs to be '''1''', but the right circuit is unsatisfiable.
CircuitSAT is closely related to [[Boolean satisfiability problem|Boolean satisfiability problem (SAT)]], and likewise, has been proven to be [[NP-complete]].<ref>{{cite web|url=http://www.cs.berkeley.edu/~luca/cs170/notes/lecture22.pdf|title=Notes for Lecture 23: NP-completeness of Circuit-SAT|author=Luca Trevisan|date=November 29, 2001|access-date=February 4, 2012|archive-date=December 26, 2011|archive-url=https://web.archive.org/web/20111226032218/http://www.cs.berkeley.edu/~luca/cs170/notes/lecture22.pdf|url-status=dead}}</ref> It is a prototypical NP-complete problem; the [[Cook–Levin theorem]] is sometimes proved on CircuitSAT instead of on the SAT, and then CircuitSAT
==Proof of NP-Completeness==
| |||