NPfullständiga

NP-fullständiga, eller NP-complete, problem är en särskild kategori av beslutproblem inom beräkningskomplexitet. Ett problem L är NP-fullständigt om två villkor uppfylls: (1) L tillhör NP, dvs. en given lösning kan verifieras i polynomisk tid; (2) varje problem i NP kan polynomiskt reduceras till L. Det innebär att ett effektivt polynomiskt tidslösande för något NP-fullständigt problem skulle ge effektiva lösningar för alla problem i NP.

Relationen mellan klasserna NP, NP-hard och P är central. Ett problem är NP-hard om varje problem i NP kan reduceras till det i polynomisk tid, men ett NP-hard problem behöver inte tillhöra NP. NP-fullständiga problem är därmed både i NP och NP-hard. Om något NP-fullständigt problem kunde lösas i polynomisk tid skulle P och NP sammanfalla.

Exempel på NP-fullständiga problem inkluderar SAT (sanningsvärdet för boolska uttryck) och 3-SAT; graffärgning för k≥3; Hamiltonians väg- och cykelproblem; Vertex Cover; Subset Sum; och Clique. Dessa problem används ofta som referenspunkter vid studier av algoritmers teoretiska begränsningar samt i utvecklingen av heuristik, approximationer och praktiska lösningar.

Historiskt spelade Cook och Levin avgörande roller i etableringen av begreppet NP-fullständighet. Cook visade 1971 genom Cook–Levin-teoremet att SAT är NP-fullständigt, medan Levin studerade liknande resultat oberoende. Reduktioner i polynomisk tid används för att visa att ett problem är NP-fullständigt.

Betydelse: NP-fullständiga problem fungerar som måttstolpar för svårighetsgränser inom teoretisk datalära och praktisk tillämpning, och motiverar ofta användningen av heuristik och approximationer när exakta lösningar är intractable.