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.