NP-komplett

Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. Helt uten kilder. (10. okt. 2015)

Innenfor informatikk og matematikk, er NP-komplette problemer en mengde med svært vanskelige problemer. Et problem blir ofte kalt lett dersom problemet kan løses på kort tid, og dette blir ofte målt som polynomisk tid; et vanskelig problem er et problem som ikke kan løses på kort tid. Et av matematikkens aller største åpne problemer i dag er om NP-komplette problemer er «lette». Clay Mathematics Institute utlyste i 2000 en liste på syv problemer, kalt millenniumsproblemene, og de lovet en dusør på en million dollar dersom noen kunne løse et av problemene. I 2004 ble ett av problemene løst, men spørsmålet, som er hintet mot i bildet til høyre, hvor vidt NP = P er fremdeles åpent.

Et problem er kategorisert som NP-komplett dersom det har følgende to egenskaper:

• Enhver gitt løsning av problemet kan kontrolleres raskt (i polynomisk tid), det vil si at problemet ligger i kompleksitetsklassen NP.
• ethvert annet NP-problem kan konverteres til problemet ved en modifisering av inputdataene.

Dette betyr at dersom ett av de NP-komplette problemene kan løses raskt, så kan alle NP-komplette problemer løses raskt.

Det mest karakteristiske kjennetegnet på et NP-komplett problem er at det ikke finnes noen effektiv måte å løse det på. Selv om en gitt løsning lar seg kontrollere raskt, er det mye vanskeligere å finne løsningen i utgangspunktet. Tiden algoritmer som løser et slikt problem bruker, øker svært fort sammenlignet med størrelsen på problemet. Det fører til at det tar uforholdsmessig lang tid å løse selv middels store problemer.

Et problem C er NP-komplett hvis:

1. C er i NP
2. Ethvert problem i NP kan reduseres til C i polynomisk tid