NPfullständighet

NP-fullständighet är en central begrepp inom beräknings- och komplexitetsteori. Ett beslutproblem är NP-fullständigt om det uppfyller två villkor: det tillhör NP och det är NP-hårt. NP-hårt betyder att varje problem i NP kan reduceras till det här problemet i polynomtid genom en så kallad many-one reduktion. Att ett problem tillhör NP innebär att en gissad lösning kan verifieras i polynomtid givet ett certifikat.

Cook–Levin-teoremet visade att SAT är NP-fullständigt; det första beviset för att NP-fullständiga problem existerar. Därefter har många andra problem visat sig vara NP-fullständiga, ofta genom polynomtidreduktionsminskningar från ett känt NP-fullständigt problem. Det innebär att om ett NP-fullständigt problem löses i polynomtid så kan alla problem i NP lösas i polynomtid, vilket skulle innebära att P = NP.

Vanliga exempel på NP-fullständiga problem inkluderar SAT och 3-SAT, CLIQUE, VERTEX COVER och HAMILTONIAN PATH. Även beslutsvarianten av SUBSET SUM är NP-fullständigt. Att visa att ett problem är NP-fullständigt används ofta genom att påvisa en polynomtidreduktions från ett redan känt NP-fullständigt problem till det nya problemet, samtidigt som problemet själv är i NP.

Noterbart finns det problem som är NP-hårda men inte i NP, och andra problem som inte anses vara NP-fullständiga trots att de är mycket svåra. NP-fullständighet fungerar som en teoretisk måttstock för svårighetsgrad och används för att klassificera problem och förstå när polynomtidlösningar sannolikt inte finns.

---