Construct · 1 fields · 3 citations

NP-completeness: a standalone construct

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

● anchor · a standalone construct Nearest construct by meaninghardnesscompare the meanings
How to read this

Every construct on the map is compared with every other by the meaning of its definitions, and the closest one is surfaced here. The nearest construct to NP-completeness is hardness.

Hold this as a prompt, not a verdict. Two constructs sitting close in meaning is a reason to read them side by side and decide for yourself whether they are one idea under two names. It is not proof that they are. Compare the meanings in the Collider.

NP-completeness1 CONSTRUCTNP-completenessCOOK · NP-COMPLETE

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

Computational complexity theory

The hardest problems in NP, to which every NP problem reduces

Stephen Cook's 1971 paper The complexity of theorem-proving procedures introduced the idea that certain problems in the class NP are the hardest members of that class, and proved that the Boolean satisfiability problem is one of them; the result is now known as the Cook-Levin theorem, because Leonid Levin arrived at the same idea independently in 1973. NP is the set of decision problems, questions with a yes-or-no answer, whose proposed solutions can be checked quickly, in a number of steps that grows only polynomially with the size of the input, even when finding a solution appears to require far more work. A problem is NP-complete when it belongs to NP and every other problem in NP can be converted into it efficiently, a conversion called a polynomial-time reduction, so that a fast method for the one would give a fast method for them all. Richard Karp's 1972 paper Reducibility among combinatorial problems showed that twenty-one well-known problems, from graph colouring to the travelling salesman decision problem, are NP-complete, establishing that the property is widespread rather than a curiosity. The construct marks the boundary between problems believed to be tractable and those believed to be intractable, and whether that boundary can ever be crossed is the open P versus NP question.[1][2][3]

Unit
A property of a decision problem: membership in NP together with NP-hardness under polynomial-time reduction
Recovery means
Not applicable
Measured by
Established by proof: showing the problem lies in NP, then giving a polynomial-time reduction from a problem already known to be NP-complete

Next

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

See how NP-completeness 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

complexity4 fields · 7 citationsjingle · one word, four constructsreduction5 fields · 5 citationsjingle · one word, five constructssatisfiability1 fields · 1 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
  2. Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations (pp. 85–103). Springer. https://doi.org/10.1007/978-1-4684-2001-2_9
  3. Levin, L. A. (1973). Universal sequential search problems. Problemy Peredachi Informatsii, 9(3), 115–116.

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