Noul algoritm crapă problema graficului

Un puzzle care a zăpăcit de mult computerele, iar oamenii de știință care le programează a devenit dintr-o dată mult mai ușor de gestionat.

Un nou algoritm rezolvă eficient problema izomorfismului grafic, a anunțat informaticianul László Babai pe 10 noiembrie la un seminar de combinatorică și informatică teoretică de la Universitatea din Chicago. Problema necesită determinarea dacă două seturi separate de puncte interconectate, cunoscute sub numele de grafice, sunt legate în același mod, chiar dacă graficele arată foarte diferit. În practică, algoritmii existenți pot face treaba într-un timp rezonabil, dar era posibil ca grafice extrem de complexe să facă problema insolubilă. Nu mai.

„Primul meu gând a fost că asta a fost o glumă. Am verificat luna pentru a mă asigura că nu a fost aprilie”, spune Ryan Williams, un informatician la Universitatea Stanford. „Este un salt uriaș în înțelegerea noastră a problemei.” El spune că descoperirea este potențial cel mai important progres teoretic al informaticii din mai mult de un deceniu.

Algoritmul lui Babai încă mai trebuie verificat, dar expertiza sa le oferă colegilor încredere în rezultat: el se confrunta cu problema chiar înainte de a face din ea subiectul tezei sale de doctorat din 1984. Deși problema poate părea abstractă, este un exemplu proeminent al unei clase ciudate de puzzle-uri pe care computerele le rezolvă probleme, în ciuda faptului că pot verifica rapid o soluție dacă este furnizată una. Rezultatul ar putea reverbera, de asemenea, dincolo de informatică, cum ar fi permițând chimiștilor să determine dacă moleculele complexe au aceeași structură de legare.

În terminologia matematică, „graf” este un cuvânt de lux pentru o rețea, genul de diagramă care ilustrează, de exemplu, o rețea de prieteni pe Facebook sau răspândirea unei boli. Fiecare punct, sau nod, este ca o minge de ping-pong care nu se poate distinge de orice altă minge și se conectează la una sau mai multe mingi cu sfoară. Cu o astfel de configurație, este ușor să faci două grafice inițial identice să arate foarte diferite prin deplasarea bilelor (vezi diagrama). Problema izomorfismului grafic necesită ca un computer să examineze două grafice care pot arăta foarte diferite și să determine dacă toate bilele au aceleași conexiuni. Graficele care împărtășesc această relație sunt izomorfe.

Calculatoarele au, în general, puține probleme în a determina dacă graficele sunt izomorfe. Dar chiar și pentru cei mai buni algoritmi, există un scenariu cel mai rău în care timpul de rezolvare crește aproape exponențial pe măsură ce crește numărul de noduri.

Babai susține că a dezvoltat un algoritm care evaluează chiar și cele mai complicate grafice în ceea ce se numește timp cvasipolinomial, pe care oamenii de știință în computere îl consideră rezonabil. „Nu eram nici măcar aproape de cvasipolinom”, spune Williams. Timpul de rezolvare crește în continuare odată cu numărul de noduri, dar o face mult mai treptat.

Babai a refuzat un interviu, spunând că vrea să confirme că rezultatele sale supraviețuiesc mai multor runde de grătar de la colegi. Este neobișnuit ca un matematician să anunțe un rezultat atât de important înainte de a trimite o dovadă scrisă, spune Neil Immerman, un informatician teoretic la Universitatea din Massachusetts Amherst. Dar „Babai este foarte inteligent și de încredere și unul dintre experții de top din lume în problema izomorfismului grafic”, spune Immerman. „Deci sunt sigur că a dovedit ceea ce a anunțat.”

Jeremy Kun, un informatician teoretic la Universitatea Illinois din Chicago, avertizează că „va dura ceva timp pentru ca toată lumea să trimită detaliile”. Dar a plecat impresionat după ce a participat la seminarul plin. „Majoritatea dovezilor pare a fi o muncă foarte, foarte grea, mai degrabă decât un fulger de perspectivă”, spune el.

Avansul ar putea ajuta cercetătorii să rezolve un mare mister cu privire la dacă fiecare problemă care poate fi ușor verificată poate fi, de asemenea, rezolvată cu ușurință (SN Online: 9/9/10). Până la rezultatul lui Babai, computerele ar putea verifica rapid dacă o soluție care să arate că două grafice sunt izomorfe este corectă, dar nu ar putea rezolva neapărat problema de la zero în mod eficient.

Unele probleme ușor de verificat sunt, de asemenea, rezolvabile rapid; ele aparțin unei categorii numite P, pentru timp polinomial. Altele sunt clasificate ca NP-complete (NP înseamnă timp polinomial nedeterminist) și sunt cele mai greu de spart. Problema vânzătorului ambulant (SN Online: 20.02.12) se numără printre puzzle-urile NP-complete. Izomorfismul grafic se află între ele. Williams spune că descoperirea lui Babai ar putea îmbunătăți înțelegerea zonei de graniță dintre P și NP-complet, o regiune care include probleme precum factorizarea numerelor întregi mari, care este folosită pentru securitatea Internetului.