Circuit satisfiability problem

Article
Talk

This is an old revision of this page, as edited by The Anome (talk | contribs) at 11:12, 4 February 2012 (moved Circuit satisfaction problem to Circuit satisfiability problem). 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, the circuit satisfaction problem (also known as CIRCUIT-SAT, or CSAT) is a decision problem related to the circuit satifiability of 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=474937653"