Circuit satisfiability problem

Article
Talk

This is an old revision of this page, as edited by The Anome (talk | contribs) at 10:54, 4 February 2012 (moved Circuit satisfiability to Circuit satisfaction problem over redirect). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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. WikiProject Computer Science may be able to help recruit an expert.

In theoretical computer science, circuit satisfaction problem (CIRCUIT-SAT, or CSAT) is a decision problem related to Boolean circuits.^[1] It is 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)

See also

Satisfiability problem

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Circuit_satisfiability_problem&oldid=474936118"