Spring til indhold

NP-komplet

Fra Wikipedia, den frie encyklopædi

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.
MatematikSpire
Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.
Hentet fra "https://da.wikipedia.org/w/index.php?title=NP-komplet&oldid=10083204"