Destacat »

25 octubre 2017 – 12:00

Certifica’t amb l’AQPE amb un 20% de descompte + un 10% si ets member abans del 31 de desembre!

Read the full story »
Col·legi

el Col·legi, informació rellevant sobre el COEINF, activitats, relacions i varis

Formació

formació continuada i orientació professional, convenis de formació amb altres entitats

Esdeveniments

tots els esdeveniments rellevants del sector TIC

Informes

informes, estudis, enquestes, … relacionats amb les tecnologies de la informació

Professió

món laboral, emprenedors, enginyers en informàtica, entrevistes, certificacions, deontologia, carreres professionals, …

Home » Notícies

Un informàtic teòric aconsegueix el descobriment de la dècada en el seu camp

Submitted by on 30 novembre 2015 – 17:00No Comment
Share Button

30 anys després, László Babai de la Universitat de Chicago presenta un algoritme que simplifica l’isomorfisme de grafs i podria fer trontollar el sistema d’encriptació de dades

L’afirmació d’un professor d’haver creat un algoritme que simplifica dràsticament un dels problemes més famosos de la informàtica teòrica ha fet que els experts es preparin per reconsiderar una veritat consolidada del seu camp. També ha servit com a recordatori que és possible realitzar avenços algorítmics similars que podrien debilitar els problemes difícils de resoldre que es troben al cor de la criptografia que protegeix els secrets digitals de tot el món.

Laszlo Babai

En un saló d’actes abarrotat, el professor László Babai de la Universitat de Chicago (EUA) va donar unes ponències que descriuen la seva nova solució per a un problema anomenat el isomorfisme de grafs . El problema demana a un ordinador que determini si dos grafs diferents – en el sentit d’un conjunt de “nodes” connectats a una xarxa, com un graf social – realment són representacions diferents del mateix.

Les ponències de Babai han suscitat un gran entusiasme perquè el isomorfisme de grafs és conegut com un problema extremadament difícil que durant més de 30 anys s’ha cregut que no dista molt de la classe de problemes més difícils per als ordinadors. Si Babai té raó, realment s’acosta molt més a la classe de problemes que poden resoldre els ordinadors de forma eficient, una categoria coneguda com P (veure Què vol dir ‘P vs NP’ per a la resta de nosaltres?).

“Això ha captat la imaginació de tots perquè la millora és molt gran”, diu Richard Lipton, un professor que treballa en la ciència informàtica teòrica a l’Institut de Tecnologia de Geòrgia (EUA). “Ho ha baixat a una classe d’una dificultat molt més baixa”. Després d’escoltar el reclam de Babai, el professor adjunt de l’Institut Tecnològic de Massachusetts (MIT, EUA) Scott Aaronson escriure al seu bloc que podria ser “el resultat de la dècada en la informàtica teòriques”.

Els informàtics mesuren la dificultat d’un problema en analitzar quant creixen els recursos computacionals que necessita un algoritme per resoldre – mentre augmenti la mida del problema original. El isomorfisme de grafs és considerat extremadament difícil perquè la necessitat de recursos del millor algoritme conegut augmenta exponencialment segons creix la mida dels grafs sobre els quals treballa.

Aquest algorisme va ser publicat en 1983 per Babai amb Eugene Luks de la Universitat d’Oregon (EUA). Babai afirma que el seu nou algoritme experimenta un augment molt menys pronunciat dels recursos requerits mentre s’engrandeixin els grafs sobre els quals treballa, baixant així de forma significativa la dificultat de l’isomorfisme de grafs.

Babai va refusar fer una entrevista, dient que no seria apropiat donar-los publicitat abans d’acabar de descriure els resultats detalladament en un treball i abans que aquest fos examinat pels seus iguals. Li va explicar a un assistent entusiasmat de la seva primera ponència que una prepublicació s’emetrà “molt, molt aviat”.

Lipton recomana precaució sempre que s’afirmi haver aconseguit un avanç sense la publicació d’un treball detallat, però que la reputació de Babai fa que moltes persones d’aquest camp de recerca creen que els seus resultats són reals. “Parlem d’un investigador estel·lar”, diu Lipton.

Si es confirma el resultat de Babai, l’efecte no es percebrà massa fora del món enrarit dels experts en la complexitat computacional. L’isomorfisme de grafs es pot aplicar a algunes situacions pràctiques, per exemple en buscar dins de les bases de dades d’estructures moleculars, que poden ser representades com grafs (veure Karen Márquez, 33: Ha emprat tecnologia cognitiva, intel·ligència artificial i ‘big data’ per personalitzar l’aprenentatge infantil). Però hi ha solucions alternatives a haver de resoldre el problema en totes les seves formes possibles, com l’algoritme de Babai.

Dades encriptades en perill

Un avanç similar al que afirma Babai sobre un problema d’una complexitat computacional similar a l’isomorfisme de grafs tindria unes repercussions més importants. Conegut com la factorització – la descomposició d’un nombre en tots els seus factors – representa l’encriptació més estesa per assegurar dades emmagatzemades i informacions que es desplacin per internet.

El millor algoritme conegut per a la factorització actualment es troba en una mena de dificultat similar a la que ha acollit durant tant de temps l’isomorfisme de grafs. La factorització no té algunes característiques matemàtiques que el resultat de Babai podria començar a permetre. Lipton afirma que es tracta d’un recordatori que nous algoritmes poden revocar les ortodòxies ben arrelades sobre aquest tipus de problemes.

“Si algú esbrina com fer que això s’acceleri, fins i tot de forma teòrica, seria molt preocupant per als criptògrafs”, explica. L’encriptació existent es pot trencar mitjançant l’ús d’una important potència computacional si els números utilitzats per sembrar els algoritmes d’encriptació no van ser prou grans. Un avanç algorítmic per a la factorització podria canviar el que resulta pràctic per a les agències governamentals amb accés a una important potència computacional.

Fins i tot si no resulta pràctic un millor algoritme per a la factorització, seria motiu per a un examen de consciència, diu Lipton. “Resultaria més difícil posar-se davant d’un públic i afirmar: ‘La meva encriptació és segura perquè empra la factorització”.

Font: MIT Technology Review

Aquesta web utilitza 'cookies' pròpies i de tercers per oferir-te una millor experiència i servei. Al navegar o utilitzar els nostres serveis, acceptes l'ús que fem de les 'cookies'. De tota manera, pots canviar la configuració de 'cookies' en qualsevol moment ACEPTAR
Aviso de cookies
Check Our FeedVisit Us On LinkedinVisit Us On TwitterVisit Us On Facebook