This article needs attention from an expert in Computer science. Please add a reason or a talk parameter to this template to explain the issue with the article. (February 2012) |
In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT or CSAT) is a decision problem related to Boolean circuits.[1] It has been proved to be NP-complete.[2]
References
- ^ David Mix Barrington and Alexis Maciel (July 5, 2000). "Lecture 7: NP-Complete Problems" (PDF).
- ^ Luca Trevisan (November 29. 2001). "Notes for Lecture 23: NP-completeness of Circuit-SAT" (PDF).
{{cite web}}: Check date values in:|date=(help)