NPfullstendighet

NPfullstendighet er et sentralt begrep i teoretisk informatikk som beskriver en kategori av beslutningsproblemer. Et problem er NPfullstendig hvis det ligger i klassen NP og samtidig er NP-hard, det vil si at hvert problem i NP kan reduseres til det i polynomisk tid.

NP er klassen av beslutningsproblemer der et ja-svar kan verifiseres i polynomisk tid hvis man får en riktig kandidat løsning presentert. En reduksjon mellom to problemer betyr en polynomisk tidsomforming av en instans av det første problemet til en instans av det andre, slik at svaret bevares. Hvis et problem Q er NPfullstendig, betyr det at Q er i NP og at hvert NP-problem kan reduseres til Q.

Historisk ble SAT (Boolean satisfiability) vist å være NPfullstendig ved Cook–Levin-teoremet. Siden har mange andre problemer blitt bevist NPfullstendige, ofte ved reduksjoner fra kjente NPfullstendige problemer. Eksempler inkluderer SAT, 3-SAT, Vertex Cover, Clique og Hamiltonian Cycle. For å bevise NPfullstendighet må man altså vise både at problemet er i NP og at det er NP-hard.

I praksis er NPfullstendige problemer ofte vanskelige å løse nøyaktig på store innganger. De løses vanligvis med heuristikker, eksakte algoritmer for små tilfeller, eller med approksimasjon. Uansett er betydningen av NPfullstendighet stor i teori og anvendelser, fordi det setter grenser for hva som er forventet å kunne løse effektivt. Falt hvis P = NP? Hvis et polynomisk algoritme finnes for noe NPfullstendig problem, vil det innebære at P = NP.