P=NP ?

He llegit l'article que escriu Agustín Royo a la secció “juegos matemáticos” de la revista Investigación y Ciencia del mes d'abril de 2010. Aquesta vegada exposa un dels problemes del mil·leni proposats per l'institut de recerca matemàtica Clay (Cambridge, Massachusetts): el problema al qual hom se sol refererir amb la grafia P = NP, que, com és comprensible, serà impossible, a primer cop d'ull, extraure'n algun significat si el lector no està al corrent dels problemes sobre computació. Agustín Royo, però, aconsegueix explicar-ho amb una gran claredat a qualsevol lector amb un mínim d'interès i un coneixement matemàtic elemental. En faré tot seguit un resum perquè trobo molt interessant donar-li la màxima difusió a problemes matemàtics de tanta profunditat com aquest. Vegem què vol dir això de P = NP. Comença l'autor a parlar del problema de computació conegut com el problema de la suma de subconjunts. Es tracta d'escollir un conjunt de nombres enters i, a partir dels seus elements, cal decidir si algun dels seus subconjunts no buits és tal que la suma dels elements que el formen és igual a zero. Donat un conjunt de n elements, el nombre de subconjunts no buits que es poden formar a partir d'aquest conjunt és igual a 2n -1. Un algorisme simple que examinés tots els possibles subconjunts podria haver de fer més de 2n operacions per donar una resposta a la pregunta. La dependència entre el nombre d'elements i el nombre d'operacions a realitzar – quantitat que dóna el temps de computació – és en aquest cas exponencial. Seria possible trobar un algorisme eficient que pogués decidir el problema exposat en dependència polinomial (nombre d'operacions necessàries de l'ordre de nk << 2 n, on l'exponent de la potència, k, és constant)? De fet, encara es desconeix la resposta a aquesta pregunta. Els problemes de computació que es poden resoldre (decidir) mitjançant algun algorisme amb dependència potencial constitueixen el conjunt de problemes anomenat P. Si tots els problemes estiguessin en P – si tots els problemes es poguessin resoldre mitjançant algun algorisme eficient (en temps polinomial) – seria molt poc costós, per exemple, trencar claus criptogràfiques, o fer simulacions complexes de qualsevol sistema; malauradament, com és ben evident, això no és pas així. Ara bé, hi ha un tercer conjunt de problemes de computació que anomenem NP. Per quins problemes està format ? Suposem que algú proposa una solució al problema de la suma de subconjunts (almenys un subconjunt la suma dels elements del qual és igual zero). Per bé que, de moment, no se sap si el problema de la suma de subconjunts es pot decidir en P (en temps polinomial), sí que és fàcil, no obstant, escriure un algorisme per verificar la solució proposada; un algorisme, a més, amb dependència polinomial entre el nombre d'elements a verificar i el nombre d'operacions a realitzar. El conjunt de problemes amb solució proposada i verificable en temps polinomial com ara el problema de la suma de subconjunts s'anomena NP. El que fa tan interessant el problema de la suma de subconjunts és el fet que es pot demostrar que qualsevol problema en NP es pot reduir al problema de la suma de subconjunts. D'aquí sorgeix un interessant repte matemàtic: si es pogués trobar un algorisme eficient (temps polinomial) per resoldre el problema de la suma de subconjunts, quedaria demostrat que tot problema en NP és, de fet, un problema en P (NP = P). Referències: ROYO, A.   P=NP. Problema del milenio, (Juegos Matemáticos), Investigación y Ciencia, abril de 2010.