NP-volledig
Uit Wikipedia, de vrije encyclopedia
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.
Principes |
Computationele complexiteitstheorie |
Modellen |
Algoritme |
Turingmachine |
Lambdacalculus |
Theorieën |
Berekenbaarheid |
Complexiteitsgraad |
NP-volledig |
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.