NPfullständigt

NP-fullständigt, ofta kallat NP-complete, är en klass beslutsproblem som uppfyller två villkor: problemet tillhör NP och problemet är NP-hårt. NP står för icke-deterministisk polynomisk tid och innebär att ett ja-svar kan verifieras i polynomtid om man får ett certifikat. NP-hårt betyder att varje problem i NP kan reduceras till det i polynomtid. En NP-fullständig uppgift anses därmed bland de svåraste i NP eftersom varje NP-problem kan omvandlas till den.

Definitioner: Ett problem är i NP om det finns en polynomisk verifieringsrutin för varje ja-svar. Ett problem är NP-hårt om varje problem i NP kan reduceras till det i polynomtid. NP-fullständigt betyder att båda villkoren gäller samtidigt: problemet är i NP och NP-hårt.

Exempel: SAT (boolesk satisfiability) är NP-fullständigt; 3-SAT är NP-fullständigt; CLIQUE, Vertex Cover och Hamiltonian Path eller Hamiltonian Cycle samt graffärgning för tre färger är vanliga NP-fullständiga problem. SAT bevisades NP-fullständigt genom Cook–Levin-teoremet.

Relation till P vs NP: Frågan om P är lika med NP är öppen. Om P=NP skulle varje NP-fullständigt problem kunna lösas i polynomtid, vilket skulle förändra mycket av datorvetenskapen. Många forskare antar att P≠NP.

Betydelse och användning: NP-fullständiga problem används som modell för svåra besluts- och optimeringsproblem inom datavetenskap, matematik och teknik. Eftersom de sannolikt inte kan lösas exakt i polynomtid används ofta heuristik, approximationer och specialiserade algoritmer för praktiska storlekar.