NP-Completeness

Definitions

A class of decision problems that are both in NP, meaning a proposed solution can be verified in polynomial time, and NP-hard, meaning every problem in NP can be reduced to them in polynomial time. They are therefore the hardest problems in NP: a polynomial-time algorithm for any one of them would give one for all of NP and prove P equals NP, the most famous open question in computer science. Stephen Cook and Leonid Levin independently showed in the early 1970s that Boolean satisfiability (SAT) is NP-complete, and Richard Karp's 1972 paper added 21 more, including graph colouring, the decision version of the travelling salesman problem, and subset sum, with thousands identified since. NP-complete does not mean unsolvable in practice: real instances are often handled with approximation algorithms, heuristics, fixed-parameter methods, and modern SAT solvers. NP-hard problems that are not in NP, such as optimisation versions, are outside the class.
In plain English: A class of problems where checking an answer is easy but finding the answer is believed to be fundamentally slow.
Example: "The traveling salesman problem is NP-complete — don't try to find the optimal route for 1,000 cities, use an approximation algorithm."