NPcomplete

NP-complete is a class of decision problems in computational complexity theory. A problem is NP-complete if it satisfies two conditions: it is in NP, and it is NP-hard. Being in NP means that given a candidate solution, its validity can be verified in polynomial time. Being NP-hard means that every problem in NP can be transformed into it by a polynomial-time many-one reduction, so an efficient solution to any NP-complete problem would yield efficient solutions to all problems in NP.

Key to the concept are polynomial-time reductions, specifically many-one reductions. A reduction from problem A to problem B maps instances of A to instances of B such that yes/no answers correspond, preserving correctness and computability in polynomial time. If a polynomial-time algorithm exists for any NP-complete problem, it would imply P = NP, since all NP problems could be solved in polynomial time via this reduction framework.

Historically, Cook’s theorem (1971) established that the satisfiability problem (SAT) is NP-complete, and Stephen Karp expanded the list of NP-complete problems. Classic examples include SAT, 3-SAT, Clique, Vertex Cover, Hamiltonian Path, and Subset Sum.

NP-complete problems are central in theoretical and applied contexts because they epitomize computational hardness for decision tasks. In practice, exact algorithms are feasible only for small instances or special cases; for larger instances, researchers rely on heuristics, approximation methods for related optimization problems, or problem-specific restrictions.

In short, NP-complete problems are the hardest problems in NP in the sense that every NP problem can be reduced to them in polynomial time, and they lie at the core of the P versus NP question.