NP-complet

De Viquipèdia
Dreceres ràpides: navegació, cerca

En complexitat computacional, el conjunt de problemes NP-complets representa el subconjunt de problemes de tipus NP més difícils de resoldre. Aquesta classificació és deguda al fet que:

  • Qualsevol problema de tipus NP es pot reduir a un problema de tipus NP-complet.
  • Com a conseqüència, trobar una solució en temps polinòmic a un problema NP-complet resoldria qualsevol problema NP en temps polinòmic, resolent el problema P=NP.

Un exemple de problema NP-complet és el problema del viatjant de comerç.