Construct · 1 fields · 1 citations

satisfiability: a standalone construct

One name. One construct. A landmark on the map.

● anchor · a standalone construct Nearest construct by meaning·not indexed
satisfiability1 CONSTRUCTSatisfiability (SAT)COOK · SAT ∈ NPC

A single standalone construct; nearby constructs are located against it in the Collider. Tap a field for its definition, unit, and measures.

Logic & computer science

Some assignment makes the formula true

In logic and computer science, a formula is satisfiable if there is at least one assignment of values that makes it true; the Boolean satisfiability problem (SAT) asks whether such an assignment exists for a given propositional formula. Cook's 1971 The complexity of theorem-proving procedures proved SAT to be NP-complete, making it the first problem shown to capture the difficulty of the whole class NP, so that every problem in NP reduces to it. The referent is both a semantic property (a formula's having a model) and the canonical hard decision problem built on that property.[1]

Unit
Whether some assignment of values makes the formula true
Recovery means
Not applicable
Measured by
Decided by exhibiting a satisfying assignment or proving none exists; computationally, the SAT decision problem

Next

Run it through the Collider, or take the citations with you.

See how satisfiability sits against neighbouring constructs in the Collider, or export every reference on this page in one click.

Open in ColliderExport BibTeXReport this entry

Nearby constructs

compactness2 fields · 3 citationsjingle · one word, two constructscomplexity4 fields · 7 citationsjingle · one word, four constructsNP-completeness1 fields · 3 citationsanchor · a standalone construct

References

  1. Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (pp. 151–158). Association for Computing Machinery. https://doi.org/10.1145/800157.805047

Cited on this page?

Confirm your construct, or correct us.

If your work is cited behind one of these entries, you know better than we do whether we captured the meaning right. Confirm it, suggest an edit, or dispute it, and your name goes on the entry as an author who has checked it, linked to your ORCID.

Claim your construct