Concepts

NP-Completeness

N-P dash completeness, read as separate letters N P

Complexity Class

Citation Formats

General Reference

Computing Atlas. "NP-Completeness." Accessed August 30, 2026. https://dev-computing.interactiveatlas.org/concepts/np-completeness.

APA Style

Computing Atlas. (n.d.). NP-Completeness. Retrieved August 30, 2026, from https://dev-computing.interactiveatlas.org/concepts/np-completeness

BibTeX

@misc{computingatlas-np-completeness,
  author = {Computing Atlas},
  title = {NP-Completeness},
  year = {2026},
  url = {https://dev-computing.interactiveatlas.org/concepts/np-completeness},
  note = {Accessed August 30, 2026}
}

NP-completeness is a classification for decision problems that are the hardest problems in the complexity class NP: their proposed solutions can be verified quickly, in polynomial time, and every other problem in NP can be reduced to them in polynomial time. Despite easy verifiability, no polynomial time algorithm is known for actually solving NP-complete problems, making them a central benchmark of computational hardness.

Facts

Disputed

Core Principle

If any single NP-complete problem could be solved in polynomial time, every problem in NP could be, which is the substance of the unresolved P versus NP question. 1

Whether P equals NP is one of the seven Millennium Prize Problems and remains unresolved; no known polynomial-time algorithm exists for any NP-complete problem, but this has not been proven impossible.

Origin Year

1971 1

Cross-Tradition Connections

Associated With

P versus NP

If any NP-complete problem were shown to have a polynomial-time algorithm, every problem in NP would; this is the tightest known link between the two open questions.

Source Wikipedia: NP-completeness