NP (Complexitat)

De Viquipèdia
Dreceres ràpides: navegació, cerca

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.

Introducció i aplicacions[modifica | modifica el codi]

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 dn
         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 dóna una entrada i la prova de què 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 se 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: