Σ Blog

Una de les meves primeres entrades en aquest bloc, ara fa gairebé un any, era per anunciar que el nombre de Déu (el nombre mínim de moviments necessari per resoldre qualsevol configuració del cub de Rubik) havia estat davallat fins a 26. Sabia que poc després havia baixat fins a 25, en un treball de Tom Rokicki publicat el març passat aquí, però no vaig dir res perquè aquest treball seguia les línies bàsiques del de Cooperman i Kunkle del que ja n’havia parlat: simplement, dividia l’espai de configuracions en moltíssimes més classes. Ara, llegint el darrer New Scientist al soleiet me n’enter que en Rokicki ha baixat la fita superior fins a 22, i així ho anuncia a la seva plana web. En aquest gran avanç no hi ha hagut idees noves: ha estat simplement que Sony Pictures Imageworks li ha deixat emprar un parell de centenars de computadors durant l’equivalent d’uns 60 anys de temps de CPU per poder analitzar més casos i fer més càlculs. Els mateixos ordinadors que s’havien emprat als efectes especials de Spiderman 3 o Sóc llegenda, al servei de les matemàtiques! La cosa ha estat que un directiu friki de Sony va llegir a Slashdot la notícia del treball de Rokicki de març i li va caure en gràcia, i va decidir d’oferir-li temps no usat de CPU dels seus ordinadors per poder fer més càlculs.

Rokicki reconeix que emprant durant 900 hores un supercomputador tipus el Blue Gene podria arribar a demostrar o refutar la conjectura que el nombre de Déu és 20 (es coneixen configuracions que necessiten 20 moviments, i no se’n coneix encara cap que en necessiti més), però això és somiar truites: és massa car. Així que calen idees noves. Si no teniu res més en què pensar aquest estiu, ja ho sabeu.

El nombre de Déu és el nombre mínim de moviments necessaris per
resoldre qualsevol instància del cub de Rubik, és a dir, per passar de
qualsevol configuració desordenada del cub de Rubik a la configuració
diguem-ne bàsica, on totes les cares tenen un color (per moviment
entenem un quart de volta o mitja volta d’una cara del cub). Li diuen el
nombre de Déu, perquè se suposa que Déu empraria el menor nombre
possible de moviments per resoldre el cub de Rubik.

Es coneixen configuracions que necessiten 20 moviments per resoldre-les
(és a dir, que no hi ha manera de resoldre-les amb 19 o menys), i la
conjectura és que el nombre de Déu és ‘vint-i-un parell’.

Aquest estiu, Gene Cooperman i un estudiant de doctorat, Dan Kunkle, en un treball presentat a l’ISSAC’07, han baixat la fita superior per a aquest
nombre de Déu a 26. Podeu trobar l’article original a la pàgina web que en
Kunkle ha muntat sobre el tema, i on trobareu a més un recull d’enllaços a les notícies que s’han publicat sobre aquest treball.

La demostració ha consistit essencialment a comprovar que en el graf de amb nodes totes les possibles configuració (i n’hi ha més de ) i arestes representant els moviments que passen d’una configuració a l’altre, tot node pot connectar-se a la configuració bàsica per un camí de 26 o menys arestes. Sí, és una demostració ‘amb ordinador’, tipus la teorema dels quatre colors o de la conjectura de Kepler, però com en aquests casos, no consisteix en una cerca exhaustiva de tots els camins possibles, que seria impossible atesa la magnitud de la tragèdia, sinó que la dueixen mitjançant una sèrie d’astúcies molt interessants, i molt matemàtiques: els cal primer demostrar teoremes de teoria de grups, de teoria de grafs, d’algorítmica en paral·lel, i fins i tot sobre gestió eficient de memòria. Així i tot, ha costat més de 800 hores de CPU.

Va’t aquí un problema ben curiós: trobar el nombre de Déu. Si més no, té un nom ideal per demanar subvencions.
És un problema rellevant? No ho crec, o, dit d’una altra manera més política, tant com la conjectura de Kepler.
Ara, és important aquest treball concret? Crec que sí. És clar que davallar la
fita superior del nombre de Déu és anecdòtic fins i tot per als
aficionats al cub de Rubik (de fet, encara ningú no ha trobat cap
configuració que no es pugui resoldre amb 20 moviments, prou enfora de
26). Però la gestió de grafs grans amb milions o fins i tot bilions
de nodes és un problema cada dia més rellevant: per esmentar-ne un
exemple que m’és proper (i que és el que m’ha fet llegir aquest
article, a mem si podia aprofitar qualque idea), les xarxes de
reaccions i interaccions bioquímiques que es produeixen als éssers
vius. Moltes qüestions sobre aquests grafs s’han de resoldre amb una
combinació de teoremes matemàtics (que dirigeixen, fiten fan més
eficient, … l’anàlisi del graf) i de càlculs massius
amb ordinadors el més memoriuts i potents possible.

En tot cas, per als matemàtics més purs, sempre queda el problema
bàsic: podríem trobar el nombre de Déu amb una demostració que no
involucràs càlculs massius? Qui ho sap. Però per ventura, si us voleu fer famosos, primer us convindria provar amb una demostració ‘lliure d’ordinador’ del teorema dels quatre colors.