NP-komplet

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

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.
Matematik Stub
Denne artikel om matematik er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.
Hentet fra "http://da.wikipedia.org/w/index.php?title=NP-komplet&oldid=6969779"