NP-volledig

NP-volledigheid is een concept uit de complexiteitstheorie. Het is een beschrijving van het inzicht uit de jaren 70 dat er een bepaald verband is tussen de complexiteit van een groot aantal problemen die in de wiskunde en informatica als "moeilijk" worden beschouwd.

In formele zin is een probleem NP-volledig (ook soms NP-compleet genoemd) als en slechts als

• het probleem tot de complexiteitsklasse NP behoort.
• elk ander probleem in NP in polynomiale tijd naar dit probleem kan worden gereduceerd.