NP (Complexitat)

En complexitat computacional, NP és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing no determinista usant una quantitat de temps de computació polinòmic, temps polinòmic. Equivalentment, aquest és el conjunt de problemes els quals la seva solució es pot "verificar" per una màquina de Turing determinista en temps polinòmic.^[1][2]

Introducció i aplicacions

La importància d'aquesta classe de problemes de decisió és que conté força problemes interessants de cerca i optimització, dels quals es vol saber si existeix una solució per un problema donat.

Com a exemple senzill, considerar el problema de determinar si un nombre n és nombre compost. Per nombres molt grans, és un problema força complex per resoldre'l eficientment; l'aproximació més simple requereix un temps exponencial en log n, el nombre de bits d'entrada. Per altra banda, un cop hem trobat un candidat per ser el factor de n, la següent funció respon si el candidat és un factor o no:

booleà ésFactorNoTrivial(n, d)
si n és divisible per d i
d ≠ 1 i d ≠ n
retorna cert
si no
retorna fals

si n és compost, aquesta funció retornarà cert per alguna entrada d. Si n és primer, aquesta funció sempre retorna fals, sigui quin sigui el valor d. Tots els problemes NP tenen una funció determinista com aquesta, que retorna cert només quan es dona una entrada i la prova de què l'entrada és en el llenguatge. La solució és verificable en temps polinòmic. En aquesta màquina se li diu verificador del problema.

Si es té una màquina no determinista, provar si nombre és compost o no és senzill. Es pot dividir en n branques diferents, en O(log n) passes; després, cada una d'aquestes branques criden la funció ésFactorNoTrivial(n, d) per un d. Si alguna té èxit, el nombre és compost; si no, és primer.

Per tant, la dificultat dels problemes NP és trobar la resposta de forma eficient, donada una forma eficient (en temps polinòmic) de verificar-la un cop trobada.

Altres problemes en 'NP són:

• Problema d'isomorfisme de grafs: determinar si dos grafs són isomorfs.
• El problema del viatjant: determinar una ruta que passi per tot de punts donats de forma òptima.
• Problema de satisfacibilitat booleana: on es vol determinar si certa formula en lògica proposicional amb variables booleanes es pot satisfer o no.

Viccionari

Referències

1. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
2. Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.