NP (Complexitat)

De Viquipèdia

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.

[edita] 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 d'un temps exponencial en log n, el nombre de bits d'entrada. Per altre banda, un cop hem trobat un candidat per ser el factor d'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 que l'entrada és en el llenguatge. La solució es verificable en temps polinòmic. En aquesta màquina se li diu verificador del problema.

Si es té un màquina no determinista, provar si nombre és compost o no es 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, es 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 és pot satisfer o no.