From Wikipedia, the free encyclopedia
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]
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:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.