NP-Complete

An NP-complete problem is a problem that is simultaneously in NP (solutions can be verified in polynomial time) and NP-hard (every problem in NP reduces to it in polynomial time). NP-complete problems are the hardest problems in NP: if any one of them could be solved in polynomial time, all problems in NP could be. The concept was formalized by Stephen Cook (Cook-Levin theorem, 1971), who showed that Boolean satisfiability (SAT) is NP-complete — the first proof that such problems exist. Richard Karp quickly demonstrated 21 more NP-complete problems (1972), establishing that NP-completeness is ubiquitous: the travelling salesman problem, graph coloring, integer programming, and many other problems arising in logistics, biology, economics, and engineering are all NP-complete. The practical implication is immediate: for an NP-complete problem, you face a choice between exactness and scalability. Exact algorithms run in exponential time on worst-case instances. Approximation algorithms, randomized algorithms, and heuristics offer polynomial-time alternatives at the cost of solution quality guarantees. P vs. NP remains unsolved: if P = NP, all NP-complete problems are tractable; if P ≠ NP (the dominant belief), they are fundamentally hard.