NP-complet

En complexitat computacional, el conjunt de problemes NP-complet, que són els problemes que pertanyen tant a NP com a NP-hard. En aquest context, NP vol dir "temps polinòmic no determinista". Els problemes NP-complets estan a NP, el conjunt de problemes de decisió la solució dels quals es pot verificar en temps polinòmic en una màquina de Turing no determinista. Un problema p de NP és NP-complet si cada tot altre problema de NP es pot transformar a p en temps polinòmic.[1][2]

Definició formal

Un problema de decisió C és NP-complet si:

• C és NP i
• tot problema NP és reductible a C en un temps polinòmic.

Diagrama de les classes P, NP, NP-Complet i NP-hard. El diagrama de l'esquerra és sota la suposició que P≠NP, el de la dreta amb la suposició que P=NP.

Problemes NP-Complet

Un exemple interessant és el problema del graf 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 graf G₁ és isomorf al graf G₂?
• isomorfisme entre subgrafs: el graf G₁ és isomorf a algun subgraf del graf G₂?

El problema del isomorfisme entre subgrafs és NP-complet. El primer problema se suposa que no és ni P ni 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

1. Handbook of theoretical computer science. 1st MIT Press pbk. ed. Amsterdam: Elsevier, 1994, ©1990. ISBN 0262720205. 
2. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
3. Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.