NP-complet
De Viquipèdia
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 a 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ç.
