En complexitat computacional , el conjunt de problemes NP-complet , que son els problemes que pertanyen tant a NP com a NP-hard . En aquest context, NP vol dir "temps polinomic no determinista". Els problemes NP-complets estan a NP , el conjunt de problemes de decisio la solucio dels quals es pot verificar en temps polinomic en una maquina de Turing no determinista . Un problema p de NP es NP-complet si cada tot altre problema de NP es pot transformar a p en temps polinomic. ^{[1] [2]}

Definicio formal [ modifica ]

Un problema de decisio C es NP-complet si:

• C es NP i
• tot problema NP es reductible a C en un temps polinomic.

Problemes NP-Complet [ modifica ]

Un exemple interessant es 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 vertexs. Si es considera aquests dos problemes: ^[3]

• Isomorfisme entre grafs: el graf G ₁ es isomorf al graf G₂ ?
• isomorfisme entre subgrafs: el graf G ₁ es isomorf a algun subgraf del graf G₂ ?

El problema del isomorfisme entre subgrafs es NP-complet. El primer problema se suposa que no es ni P ni NP-complet i que es un problema NP.

Altres problemes NP-complet son:

• problema del viatjant de comerc .
• problema del cami hamiltonia
• problema de satisfacibilitat booleana (SAT)

Referencies [ modifica ]