NP és la classe de llenguatges que tenen verificadors de temps polinomials
La classe NP, que significa "temps polinomial no determinista", és un concepte fonamental en la teoria de la complexitat computacional, un subcamp de la informàtica teòrica. Per entendre la NP, primer cal comprendre la noció de problemes de decisió, que són preguntes amb una resposta sí o no. Un llenguatge en aquest context fa referència a un conjunt de cadenes sobre algun alfabet, on cada cadena codifica una instància d'un problema de decisió.
Es diu que un llenguatge (L) està en NP si existeix un verificador en temps polinomial per a (L). Un verificador és un algorisme determinista (V) que pren dues entrades: una instància (x) i un certificat (y). El certificat (y) també es coneix com a "testimoni" o "prova". El verificador (V) comprova si el certificat (y) confirma que (x) pertany a la llengua (L). Formalment, un llenguatge (L) està en NP si existeix un algorisme de temps polinomial (V) i un polinomi (p(n)) de manera que per a cada cadena (x a L), existeix una cadena (y) amb ( |y|. leq p(|x|)) i (V(x, y) = 1). Per contra, per a cada cadena (x en L), no hi ha cap cadena (y) tal que (V(x, y) = 1).
Per dilucidar aquest concepte, considereu el conegut problema de la "satisfabilitat booleana" (SAT). El problema SAT pregunta si existeix una assignació de valors de veritat a variables en una fórmula booleana determinada de manera que la fórmula s'avaluï com a vertadera. El problema SAT està en NP perquè, donada una fórmula booleana ( phi ) i una assignació ( alfa ) de valors de veritat a les seves variables, es pot verificar en temps polinomial si ( alfa ) satisfà ( phi ). Aquí, la instància ( x ) és la fórmula booleana ( phi ) i el certificat ( y ) és l'assignació ( alfa ). El verificador ( V ) comprova si ( alfa ) fa que ( phi ) sigui cert, cosa que es pot fer en temps polinomial respecte a la mida de ( phi ).
Un altre exemple il·lustratiu és el problema del "Camí de Hamilton". Aquest problema pregunta si hi ha un camí en un gràfic donat que visiti cada vèrtex exactament una vegada. El problema del camí hamiltonià també es troba en NP perquè, donat un gràfic ( G ) i una seqüència de vèrtexs ( P ), es pot verificar en temps polinomial si ( P ) és un camí hamiltonià en ( G ). En aquest cas, la instància ( x ) és la gràfica ( G ), i el certificat ( y ) és la seqüència de vèrtexs ( P ). El verificador ( V ) verifica si ( P ) forma un camí hamiltonià, que es pot fer en temps polinomial respecte a la mida de ( G ).
El concepte de verificabilitat en temps polinomial és important perquè proporciona una manera de caracteritzar problemes que es poden comprovar de manera eficient, fins i tot si trobar la solució podria ser computacionalment inviable. Això condueix a la famosa pregunta de si ( P = NP ), que pregunta si tots els problemes la solució del qual es pot verificar en temps polinomial també es poden resoldre en temps polinomial. La classe ( P ) consta de problemes de decisió que es poden resoldre en temps polinomial mitjançant una màquina de Turing determinista. Si ( P = NP ), significaria que tots els problemes amb un verificador de temps polinomial també tenen un solucionador de temps polinomial. Aquesta pregunta continua sent un dels problemes oberts més importants de la informàtica.
Una de les propietats clau de NP és que està tancat sota reduccions de temps polinomial. Una reducció en temps polinomial d'una llengua ( L_1 ) a una llengua ( L_2 ) és una funció computable en temps polinomial ( f ) tal que ( x en L_1 ) si i només si ( f(x) en L_2 ). Si hi ha una reducció de temps polinomial de ( L_1 ) a ( L_2 ) i ( L_2 ) està en NP, aleshores ( L_1 ) també és en NP. Aquesta propietat és fonamental en l'estudi de la NP-completezza, que identifica els problemes "més difícils" de NP. Un problema és NP-complet si està en NP i tots els problemes en NP es poden reduir a ell en temps polinomial. El problema SAT va ser el primer problema que es va demostrar que era NP-complet, i serveix com a base per demostrar la NP-completitat d'altres problemes.
Per il·lustrar més el concepte de verificabilitat en temps polinomial, considereu el problema de la "Suma del subconjunt". Aquest problema pregunta si existeix un subconjunt d'un conjunt determinat de nombres enters que sumi un valor objectiu especificat. El problema de la suma del subconjunt està en NP perquè, donat un conjunt d'enters ( S ), un valor objectiu ( t ) i un subconjunt ( S' ) de ( S ), es pot verificar en temps polinomial si la suma dels elements en ( S' ) és igual a ( t ). Aquí, la instància (x) és la parella ((S, t)), i el certificat (y) és el subconjunt (S'). El verificador ( V ) comprova si la suma dels elements de ( S' ) és igual a ( t ), cosa que es pot fer en temps polinomial respecte a la mida de ( S ).
La importància de la verificabilitat en temps polinomial va més enllà de les consideracions teòriques. En termes pràctics, vol dir que per als problemes en NP, si es proporciona una solució proposada (certificat), es pot comprovar de manera eficient. Això té implicacions importants per als protocols criptogràfics, problemes d'optimització i diversos camps on és important verificar la correcció d'una solució.
En resum, la classe NP engloba problemes de decisió per als quals una solució proposada es pot verificar en temps polinomial mitjançant un algorisme determinista. Aquest concepte és fonamental en la teoria de la complexitat computacional i té profundes implicacions tant per als aspectes teòrics com pràctics de la informàtica. L'estudi de la NP, la verificació en temps polinomial i conceptes relacionats com ara la NP-completezza continua sent una àrea de recerca vibrant i crítica.
Altres preguntes i respostes recents sobre Complexitat:
- La classe PSPACE no és igual a la classe EXPSPACE?
- La classe de complexitat P és un subconjunt de la classe PSPACE?
- Podem demostrar que les classes Np i P són iguals trobant una solució polinomial eficient per a qualsevol problema NP complet en un TM determinista?
- La classe NP pot ser igual a la classe EXPTIME?
- Hi ha problemes a PSPACE per als quals no es coneix l'algorisme NP?
- Un problema SAT pot ser un problema NP complet?
- Pot un problema estar en classe de complexitat NP si hi ha una màquina de tornejat no determinista que el resolgui en temps polinomial
- P i NP són realment la mateixa classe de complexitat?
- És cada llenguatge lliure de context a la classe de complexitat P?
- Hi ha una contradicció entre la definició de NP com a classe de problemes de decisió amb verificadors de temps polinomial i el fet que els problemes de la classe P també tinguin verificadors de temps polinomial?
Veure més preguntes i respostes a Complexity