NP-complet -a
NP-complet -a
- ca NP-complet -a, adj
- es NP-completo
- fr NP-complet
- en NP-complete
Matemàtiques
Definition
Dit de l'algorisme de decisió que resol un problema X de tipus no determinista polinòmic (NP) i en què, per a tot Y, problema NP, es verifica que, donades dues entrades A i B que puguin construir-se una de l'altra en temps polinomial respecte de l'original, A fa que X tingui resposta afirmativa només si B fa que Y tingui resposta afirmativa.
Note
- NP prové de l'expressió no determinista polinòmic.
