De 21 problemene NP-komplett Karp markerte en milepæl i historien om algoritmens kompleksitetsteori . Dette er 21 problemer som er kjent for å være vanskelige i kombinatorikk og grafteori som kan reduseres mellom dem. Dette ble demonstrert Richard Karp i 1972 i sin artikkel reduserbarhet blant kombinatoriske problemer , samt deres NP-fullstendighet.
En av de viktigste resultatene i kompleksitetsteori er Stephen Cook i 1971 . I sin artikkel viser han det første NP-komplette problemet , nemlig SAT-problemet (se Cooks teorem ). Det er denne ideen Karp utvikler ved å bruke den på kombinatorikk og grafteoriske problemer.
De 21 problemene er organisert i fordypninger for å indikere retningen på reduksjonen som ble brukt for å bevise deres NP-fullstendighet. For eksempel har ryggsekkproblemet vist seg å være NP-komplett ved en reduksjon fra eksakt dekning .
Det originale engelske navnet er i store bokstaver.