Revision as of 10:52, 4 February 2012 edit The Anome (talk \| contribs) Edit filter managers, Administrators 260,268 edits In theoretical computer science, ← Previous edit		Revision as of 10:54, 4 February 2012 edit undo The Anome (talk \| contribs) Edit filter managers, Administrators 260,268 edits '''circuit satisfaction problem''' Next edit →
Line 1: {{expert-subject\|Computer Science}} In theoretical computer science, '''~~Circuit~~circuit ~~satisfiability~~satisfaction problem''' ('''CIRCUIT-SAT''', or '''CSAT''') is a [[decision problem]] related to [[Boolean circuit]]s.<ref>{{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> It is [[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}}</ref> == References ==

Circuit satisfiability problem: Difference between revisions