NPkompletta

NP-complete, commonly written NP-complete, is a class of decision problems that are in NP and NP-hard. A problem is in NP if a proposed solution can be verified in polynomial time. A problem is NP-hard if every problem in NP can be reduced to it by a polynomial-time reduction; such problems are at least as hard as the hardest problems in NP. If a problem is both in NP and NP-hard, it is NP-complete.

Proving NP-completeness typically requires two steps: (1) show the problem lies in NP, and (2) provide a polynomial-time reduction from a known NP-complete problem to it. The Cook–Levin theorem established that SAT is NP-complete; since then many problems have been shown NP-complete via reductions. Canonical NP-complete problems include SAT, 3-SAT, CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE, SUBSET SUM, and PARTITION.

Implications and context: If any NP-complete problem has a polynomial-time algorithm, then every problem in NP has one (P = NP). While most researchers believe P ≠ NP, this remains unproven. In practice, NP-complete problems are approached with heuristics, exact algorithms that perform well on small instances, restricted cases where they become tractable, or via approximation and parameterized methods. NP-completeness provides a framework for understanding why many seemingly simple questions about graphs, logic, and combinatorics resist efficient algorithms in the worst case, while allowing targeted strategies for practical instances.