Col·laboracions

Dins del cicle de conferències "Les grans conjectures matemàtiques. Reptes matemàtics per al Segle XXI" el passat dimecres dia 6 de maig el Dr. Avi Wigderson, de l'Institute of Advanced Studies de Princeton (USA), va presentar "El problema P versus NP i els límits del coneixement" Tenia una gran curiositat per escoltar a un investigador tan reconegut com el Dr. Wigderson explicant a un públic, que podia ser neòfit en Teoria de la Computació, una qüestió de tanta transcendència com és la de 'P versus NP'.

Per a mi va ser un plaer únic veure com es podia descriure d'una manera tan entenedora i intuïtiva la qüestió central en Theoretical Computer Science plantejada des de fa aproximadament quatre dècades. El Dr. Wigderson va centrar el discurs en mostrar la forta relació entre computació, naturalesa, matemàtiques, algorismes, bellesa i eficiència. La seva tesi es basava en tres idees fonamentals: la computació és present arreu, els algorismes constituiexen el llenguatge de la computació, i la creativitat no pot ser automatitzada (traducció intuïtiva, segons el Dr. Wigderson, de la conjectura P diferent de NP).

Una vella qüestió presentada amb una elegància i senzillesa que només ho pot fer possible algú que té un coneixement profund de les capacitats i limitacions de la computació. El Dr. Wigderson va transmetre amb entusiasme la bellesa de molts conceptes de Teoria de la Complexitat Computacional, introduïts tots ells en l'intent de resoldre P versus NP.

Seguidament resumiré la seva conferència així com també algunes de les respostes que va donar a preguntes plantejades pel públic. Si bé la conferència estava adreçada a un públic general, el torn de preguntes va fer palès que molts dels assistents tenien un coneixement previ i bastant profund de la qüestió.
Comença el discurs dient que la computació és present a tot arreu, es podria enumerar una llarga llista de fenòmens naturals i reptes intel·lectuals que tenen com a component essencial la computació. D'entre molts exemples que va donar recordo el de l'home calb resultant del procés natural de pèrdua de cabells, els primers mesos de creixement d'un fetus, el procediment de sumar nombres decimals de moltes xifres, els canvis climàtics, etc. I la pregunta és: què tenen en comú aquests processos? En tots ells hi ha un subjecte, que anomenem entrada, al que se li apliquen unes accions molt ben determinades i mitjançant les quals l'entrada es va modificant per obtenir al final el producte resultant o sortida. La naturalesa obté a la fi el producte resultant d'aquests processos. Podem nosaltres definir sempre un procediment que ens permeti obtenir el resultat desitjat? Té algun límit la computació? Per exemple, hi ha una manera mecànica i efectiva de resoldre equacions, disposem d'un procediment mecànic per demostrar teoremes? Primer cal que es defineixi de manera precisa com descriure aquests procediments o computació.
Els algorismes constitueixen el llenguatge que descriu la computació. Per exemple, els dos algorismes que ens ensenyen a l'escola de primària, el de sumar i el de multiplicar dos nombres naturals. Aquests algorismes descriuen pas a pas com realitzar aquesta suma o producte, cada pas és una operació bàsica sobre dígits decimals, i és independent del nombre de xifres. Un algorisme és un conjunt finit d'instruccions que es poden aplicar a una infinitat d'entrades, descriuen una procediment de càlcul. Es proposa la Màquina de Turing com un model formal d'algorisme. La Tesi de Church-Turing diu que tot algorisme pot ser descrit formalment per una Màquina de Turing i aquesta tesi es va mantenint des de ja fa uns 70 anys. Aleshores hom pot plantejar rigorosament el poder delimitar quines limitacions té la computació. Problemes tan naturals com el de demostrar teoremes són incomputables, o dit intuïtivament, les demostracions de teoremes no es poden fer de manera automàtica.
Tornant a l'exemple dels algorismes de la suma i producte, aprofita per fer notar que el nombre d'operacions bàsiques que realitza cadascun d'ells depèn directament del nombre de dígits dels dos nombres d'entrada. El de la suma realitza un nombre constant d'operacions per cada dígit mentre que l'algorisme de la multiplicació, per cada dígit en realitza tantes com el nombre de dígits del número més llarg multiplicat per una constant. Altres algorismes que es comporten d'una manera semblant en tant que realitzen un nombre d'operacions raonable per computar la solució són els que resolen problemes com els de calcular els camins més curts entre dos punts, problemes de reconeixement de patrons i el càlcul de la FFT. Tots ells permeten computar les solucions desitjades, són algorismes astuts, elegants i eficients que permeten resoldre que problemes que han estat gens trivials. Tots aquests problemes formen part de la classe P, la classe de problemes per als que computar una solució es pot fer de manera eficient.

Contrastant amb aquests exemples ens fa notar que és fàcil verificar que 193707721 x 761838257287=147573952589676412927, només cal fer una multiplicació de dos nombres llargs. En canvi si l'entrada és el número 147573952589676412927 i el que volem és computar els seus factors primers, el procediment de provar tots els possibles factors no seria gens eficient. Si el nombre d'entrada té n dígits aleshores es farien unes 2 ^(n/2) proves en el cas pitjor i a la pràctica no no veuríem acabar la computació.

Tots el problemes pràctics tenen aquestes característiques? En aquest punt el Dr. Widgerson provoca a l'audiència demanant-nos si juguem a resoldre Sudokus. I si ho fem és per què ens diverteix senzillament, o per què ens agradaria fer una aportació a la ciència. Com en el cas anterior, si juguéssim a Sudokus de dimensions qualssevol n x n, seria molt diferent el verificar que una solució és correcta, de trobar-la. Aplicant 'força bruta' com en el cas de la factorització, l'algorisme no seria efectiu a la pràctica. El mateix a l'hora de demostrar teoremes que sí tenen demostració i que aquesta no és massa llarga. Si es dona la demostració, verificar que és correcta és fàcil. Aquests tres problemes formen part de la classe NP, la classe de problemes per als que si es dona una possible solució, és fàcil comprovar que és correcta.

Un cop definides intuïtivament aquestes classes P i NP ja pot atacar la qüestió P versus NP. És clar que tot problema que està en la classe P també està en la classe NP. Si es pot computar la solució aleshores es pot verificar. La conjectura és que computar solucions és molt més difícil que verificar-les, P ≠ NP. Si P=NP aleshores aquestes solucions es podrien computar de manera eficient. És més, en el cas del Sudoku si fóssim capaços de dissenyar un algorisme que computés ràpidament, aleshores P=NP, qualsevol problema de la classe NP es pot traduir a problema de solucionar Sudokus. El mateix passaria amb el problema de demostrar teoremes amb demostracions d'una certa longitud. Aquesta idea intuïtiva de que un problema captura tota la complexitat de la classe NP correspon al concepte formal de NP-completesa.

Per acabar amb l'exposició de la rellevància de P=NP? el Dr. Wigderson fa la consideració següent. Si existís un algorisme eficient per resoldre Sudokus, factoriztar nombres seria fàcil. Això tindria un impacte molt negatiu en els sistemes de seguretat en transaccions electròniques, serien clarament vulnerables. El 'bread and butter' de tot investigador en Teoria de la Computació és dissenyar algorismes eficients per a problemes no trivials o bé demostrar la impossibilitat de la seva existència. En el cas de la factorització encara no s'ha pogut demostrar cap de les dues coses.

Els algorismes eficients són pedres precioses. Molts problemes que antigament es pensava que no tenien solució a la fi han pogut ser resolts. Els algorismes que computen la solució en tots aquest casos són elegants, astuts i independents de la tecnologia. P versus NP: és més fàcil verificar una solució que trobar-ne una qualsevol? El Dr. Wigderson creu que P=NP és una utopia. Si fos així molta part de la ciència podria ser automatitzada... I que P≠NP ... pot ser algun dia ho veurem.

Del torn de preguntes voldria remarcar que el Dr Wigderson va contestar cadascuna d'elles d'una manera molt intuïtiva i, crec jo, convincent. Totes elles se centraven en el significat de la qüestió P versus NP en àmbits diferents. En recordo dues en particular, sobre tot per la claredat de les respostes donades i també perquè ressaltaven una vegada més l'esforç que s'està fent per entendre les limitacions de la computació.

Una d'elles va ser en relació a la computació i naturalesa i deia: Es veritat que la naturalesa pot resoldre eficientment problemes NP-complets?' El Dr Wigderson va respondre que si bé era cert que en els éssers vius contínuament s'estan resolent problemes que hom ha classificat NP-complets, cal dir que cada individu té unes dades molt particulars que el caracteritzen, que el defineixen. Aleshores les solucions computades en cada cas no tenen com a dades d'entrada totes les possibles, sino que en cada individu es calcula la solució per un subconjunt restringit de dades. Cada individu 'resol' el seu problema 'particular' i de manera molt eficaç.

L'altra pregunta que voldria esmentar va ser la següent: Quin impacte ha tingut la caracterització de NP en termes de PCPs? El Dr Wigderson primer va explicar d'una manera molt planera, cosa que sembla gairebé impossible, què vol dir que 'Cada conjunt a NP té un sistema PCP '. El nom PCP prové de Probabilistic Checkable Proof system. Imaginem-nos que tenim una demostració d'un teorema que té unes 200 pàgines i volem verificar que és correcta. Tot seguit la 'normalitzem' d'una manera molt particular i passa a ser una demostració d'unes 2000 pàgines, una mica més llarga, però no exageradament més llarga. El sistema PCP és un verificador probabilístic que rep entrades d'aquest tipus, però ara aquest verificador només pot llegir una petita part d'aquesta demostració (que serà sel·leccionada aleatòriament). Una analogia podria ser la d'un revisor que intenta decidir la correctesa d'una demostració molt llarga triant de manera aleatòria només unes poques línies de la demostració. Aquest mètode sembla inadequat, com es pot assegurar que hi ha algun error sense haver llegit completament tota la demostració? Aquesta intuïció és vàlida quan considerem només la manera "natural" d'escriure les demostracions, però falla quan s'utilitzen certs formats "robusts" de les demostracions (i com és natural, s'admet una probabilitat petita d'error). Aquests sistemes de demostracions robustes són els anomenats PCPs. Un sistema d'aquest tipus per a un conjunt S és un verificador probabilístic eficient (ràpid) que té accés a uns pocs bits de la suposada demostració en format robust. El verificador llença a l'aire una moneda i d'acord amb el resultat accedeix a un nombre constant de bits de la suposada demostració. Cada element del conjunt S ha de ser acceptat amb probabilitat 1 (donada una demostració real, correctament codificada), i rebutja qualsevol element que no pertanyi a S amb probabilitat com a mínim 1/2 (no importa quina sigui la suposada demostració donada en format robust). El famós teorema diu que cada conjunt NP té un sistema PCP i, a més, existeix un algorisme eficient que tradueix qualsevol possible demostració o testimoni de pertinença a un conjunt NP a una demostració en format "robust".

Segons el Dr Wigderson la demostració del teorema PCP suggereix una nova manera d'escriure demostracions "robustes" en la que qualsevol error (virus) s'escampa per tot arreu. I si la probabilitat de trobar un error en aquests pocs bits de l'entrada és molt petita, aleshores el teorema és correcte. I per acabar, el Dr Wigderson remarca una de les implicacions d'aquesta caracterització: 'Sota la hipòtesi P diferent de NP, aleatoritzar no ajuda'.
alvarez@lsi.upc.edu
ilapuente@lsi.upc.edu