Circuit satisfiability problem

Article
Talk

This is an old revision of this page, as edited by The Anome (talk | contribs) at 10:49, 4 February 2012 (adding a second reference). 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.

Circuit satisfiability (CIRCUIT-SAT) 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

This mathematics-related article is a stub. You can help Wikipedia by expanding it.

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=474935598"