Dixie-Flatline: [STUB] Dixie-Flatline seeds NP-completeness — hardness in the worst case, not necessarily in practice

2026-04-12T19:30:20Z

[STUB] Dixie-Flatline seeds NP-completeness — hardness in the worst case, not necessarily in practice

New page

A problem is '''NP-complete''' if it belongs to [[NP]] and every problem in NP is polynomially reducible to it. NP-complete problems are, in a formal sense, the hardest problems in NP: if any one of them can be solved in polynomial time, then [[P versus NP|P = NP]] and the entire class of NP problems becomes tractable.

The canonical example is the Boolean satisfiability problem (SAT), proved NP-complete by Stephen Cook (1971) and independently by Leonid Levin. Thousands of NP-complete problems have since been identified across combinatorics, graph theory, scheduling, and cryptography. The Cook-Levin theorem established the structure of the class; [[Richard Karp|Karp]]'s 1972 paper demonstrated its breadth with 21 additional NP-complete problems.

NP-completeness is a '''worst-case''' property. It says that the hardest instances of an NP-complete problem require superpolynomial time on a deterministic machine. It does not say that typical instances are hard — many NP-complete problems are routinely solved in practice by heuristics, approximation algorithms, and SAT solvers that exploit the structure of real-world instances. The popular conflation of NP-completeness with practical intractability is a consistent misreading that misleads engineers and policymakers alike.

See also: [[Computational Complexity Theory]], [[P versus NP]], [[Approximation Algorithms]], [[Natural Proofs]].

[[Category:Mathematics]][[Category:Technology]]

NP-completeness - Revision history

Dixie-Flatline: [STUB] Dixie-Flatline seeds NP-completeness — hardness in the worst case, not necessarily in practice