A fost publicat un algoritm rapid pentru problema izomorfismului grafic
Matematicianul László Babai de la Departamentul de Informatică și Matematică de la Universitatea din Chicago a dezvăluit un nou algoritm rapid pentru rezolvarea problemei izomorfismului grafic, una dintre problemele fundamentale în teoria complexității computaționale. Algoritmul aduce problema foarte aproape de clasa P. Potrivit unor experți, acesta este unul dintre cele mai semnificative rezultate din informatica teoretică într-un deceniu, dacă nu chiar câteva decenii. Laszlo a anunțat crearea algoritmului în urmă cu o lună. Potrivit acestuia, algoritmul este mult mai eficient decât cel mai bun algoritm existent, care a deținut recordul timp de mai bine de treizeci de ani: a fost dezvoltat de acum profesorul Eugene Lux în 1983, care a rezolvat problema în timp subexponențial.
Laszlo Babai, aparent, a reușit să reducă practic problema la o problemă de clasă P: algoritmul său este declarat a fi calculabil în timp cvasi-polinomial.
Timp de câteva decenii, problema izomorfismului grafului a avut un statut special în teoria complexității computaționale. În timp ce sute de alte probleme au cedat cu blândețe clasei P sau clasei NP, problema izomorfismului grafic nu a putut fi clasificată fără ambiguitate. Părea a fi mai greu decât problemele ușoare și mai ușor decât cele dificile, ocupând o poziție unică, parcă între două clase de probleme. Este una dintre cele două probleme celebre din acest domeniu intermediar ciudat, spune Scott Aaronson, un matematician la Institutul de Tehnologie din Massachusetts. Acum, în cuvintele sale, „se pare că unul dintre cei doi a renunțat”.
A doua problemă binecunoscută din zona „gri” este factorizarea numerelor întregi.
Problema izomorfismului grafic în sinearată simplu: trebuie să determinați dacă două grafice sunt izomorfe, adică dacă este posibil să transformați un grafic în altul prin simpla mutare a vârfurilor, menținând în același timp conexiunile între vârfuri. Asta e tot. În ciuda simplității sale aparente, această problemă este dificil de rezolvat, deoarece chiar și graficele mici pot lua multe forme diferite.
Algoritmul lui Laszlo Babay funcționează prin „colorarea” virtuală a vârfurilor unui grafic. În primul rând, mai multe vârfuri sunt selectate aleatoriu, sunt „pictate” în culori diferite. Apoi sunt selectate mai multe vârfuri din al doilea grafic, presupus corespunzătoare vârfurilor din primul grafic, li se atribuie aceleași culori. În cele din urmă, toate opțiunile sunt rezolvate. După selecția inițială, algoritmul colorează vârfurile presupus izomorfe adiacente celor selectate inițial în culori diferite pe ambele grafice până când nu există conexiuni între vârfuri.
Problema izomorfismului grafic este considerată „universală”, adică orice problemă poate fi redusă la ea, unde se pune problema izomorfismului structurilor combinatorii. De obicei, o astfel de „universalitate” este caracteristică problemelor clasei NP. În același timp, problema izomorfismului grafului a prezentat o proprietate ciudată pe care nicio altă problemă NP-completă nu o are: trecerea „testului orb” (protocolul Arthur-Merlin).
Laszlo Babai a lucrat la problema izomorfismului grafic timp de aproape 40 de ani.