NP-complet
Encomplexitat computacional,el conjunt de problemesNP-complet,que són els problemes que pertanyen tant aNPcom aNP-hard.En aquest context, NP vol dir "temps polinòmic no determinista". Els problemes NP-complets estan aNP,el conjunt de problemes de decisió la solució dels quals es pot verificar entemps polinòmicen unamàquina de Turing no determinista.Un problemapde NP és NP-complet si cada tot altre problema de NP es pot transformar apen temps polinòmic.[1][2]
Definició formal
[modifica]Un problema de decisió C és NP-complet si:
- Cés NP i
- tot problema NP és reductible aCen un temps polinòmic.
Problemes NP-Complet
[modifica]Un exemple interessant és el problema delgraf isomorf,el problema de teoria de grafs de saber si hi ha isomorfisme entre dos grafs. Dos grafs son isomorfs si un es pot transformar en l'altre tan sols rebatejant el nom dels vèrtexs. Si es considera aquests dos problemes:[3]
- Isomorfisme entre grafs: el grafG1és isomorf al grafG₂?
- isomorfisme entre subgrafs: el grafG1és isomorf a algun subgraf del grafG₂?
El problema del isomorfisme entre subgrafs és NP-complet. El primer problema se suposa que no és niPni NP-complet i que és un problema NP.
Altres problemes NP-complet son:
- problema del viatjant de comerç.
- problema del camí hamiltonià
- problema de satisfacibilitat booleana(SAT)
Referències
[modifica]- ↑Handbook of theoretical computer science.1st MIT Press pbk. ed. Amsterdam: Elsevier, 1994, ©1990.ISBN 0262720205.
- ↑Michael.,Sipser,.Introduction to the theory of computation.3a edició. Boston, MA: Cengage Learning, 2013.ISBN 9781133187790.
- ↑Peter.,Linz,.An introduction to formal languages and automata.5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012.ISBN 9781449615529.
| Considerades tractables | |
|---|---|
| Suposadament intractables | |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
