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
Vanliga exempel på NP-fullständiga problem inkluderar SAT och 3-SAT, CLIQUE, VERTEX COVER och HAMILTONIAN PATH. Även
Noterbart finns det problem som är NP-hårda men inte i NP, och andra problem som inte anses
---