NP-komplet

Inden for kompleksitetsteori i datalogi, er kompleksitetsklassen NP-komplet (forkortet NP-C eller NPC, hvor NP står for non-deterministisk polynomiel tid) en klasse af problemer der har følgende to egenskaber:

• Enhver løsning til problemet kan verificeres i polynomiel tid.
• Hvis problemet kan løses i polynomiel tid, så kan alle problemer i NP løses i polynomiel tid.

Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.