Guardó per al matemàtic que es va rendir davant dels ordinadors

Stephen Cook ha estat distingit amb el Premi Fronteres del Coneixement de Tecnologies de la Informació.
Alan Turing va descriure per primera vegada al 1936 el concepte de computabilitat i va detallar quins problemes pot resoldre, o no, un ordinador. A aquesta idea, el matemàtic Stephen Cook (Nova York, 1939) va afegir l'eficiència: saber si un problema es pot resoldre en un temps assumible -i el temps és la clau- és essencial per decidir si val la pena insistir en solucionar-ho o resignar-se i buscar una conclusió aproximada. Amb aquesta idea, el matemàtic ha guanyat el Premi Fronteres del Coneixement de Tecnologies de la Informació, atorgat per la Fundació BBVA.

Stephen Cook ha aconseguit el guardó per determinar que hi ha problemes que els ordinadors no poden resoldre de manera eficient. “En aquest cas, el més intel·ligent és deixar d'intentar-ho. Això permet als programadors assajar estratègies molt més útils”, explica Cook.

En concret, el matemàtic va dividir els problemes en dues categories: els que es poden resoldre en un temps raonable, als quals va anomenar P, i aquells que implicarien tant de temps que “el sol s'apagaria abans”, als quals va anomenar NP.
Per aquests últims va definir una subclasse: els problemes NP-complets. En aquesta categoria hi ha els enigmes més difícils que, a més, són equivalents. És a dir, que si es trobés una solució per un d'ells, significaria que hi ha una solució per a tots els altres.

Actualment, hi ha milers de problemes NP-complets en àmbits molt diversos: biologia, física, economia, teoria de nombres, lògica … Un exemple és la forma en què les proteïnes adquireixen la seva estructura tridimensional, un problema essencial en biologia. Un altre és el famós enigma del viatjant: trobar la ruta més eficient que ha de seguir un repartidor per arribar a tots els destinataris.
Stephen Cook planteja amb aquesta investigació un dels grans Problemes del Mil·lenni: els principals enigmes sense resoldre de les matemàtiques la solució dels quals està recompensada amb un milió de dòlars: hi ha una solució eficient per als problemes NP-complets?
Els 45 anys d'esforços combinats d'informàtics i matemàtics no han servit per a trobar la solució. La immensa majoria dels experts creu que no hi ha un algoritme que resolgui els problemes NP. El Problema del Mil·lenni que va plantejar Cook es diu P versus NP, és a dir, enigmes que tenen solució contra els que no la tenen.

Per exemple, en la qüestió del viatjant, l'única manera de trobar la ruta més ràpida per visitar a tots els comerciants és calcular totes les trajectòries possibles: cal fer tants càlculs que, en la pràctica, és irresoluble. El Problema del Mil·lenni plantejat per Cook es pregunta si de debò no hi ha cap manera més ràpida, cap drecera brillant, que permeti resoldre aquests problemes NP-complets.
Si algú descobrís la fórmula màgica que solucionés un enigma NP-complet, podria solucionar tots. Això comprometria, per exemple, els sistemes de xifrat i la seguretat dels bancs i Internet, on s'utilitzen problemes NP-complets -que fins ara no es poden resoldre- per mantenir les claus i les rutes d'accés sota màxima seguretat.
Stephen Cook és catedràtic de Ciències de la Computació a la Universitat de Toronto (Canadà). Va publicar el seu estudi més influent al 1971, en què analitzava i intentava resoldre un problema NP qualsevol. En aquest moment no era conscient de quants enigmes d'aquest tipus existien. Només un any després, un altre investigador va publicar una llista amb 300 problemes NP més. El matemàtic sabia que el concepte amb el qual estava treballant era interessant, “però no tenia ni idea que seria tan important”, explica Cook.


Font: Associació Catalana d'Empreses d'Informàtica