Informaticienii sunt mai aproape de obiectivul algoritmic major | Revista Quanta

Dacă cineva vă cere să determinați dacă două obiecte sunt la fel, ar putea părea o solicitare banală. În cele mai multe cazuri de zi cu zi, o privire rapidă este suficientă pentru a da o judecată exactă.

Dar în informatică, este o întrebare mult mai implicată. De fapt, este unul care reduce la inima nerezolvată a ceea ce sunt capabile computerele. În funcție de obiectele și de modul în care definiți asemănarea, încă nu știm dacă computerele pot răspunde rapid la întrebare sau dacă o abordare lentă și laborioasă este în esență cea mai bună pe care o pot gestiona.

În ultimul deceniu, au existat câteva rezultate importante care demonstrează că computerele pot face cel puțin mai bine decât atât. Unul dintre cele mai mari rezultate recente în informatică a fost un algoritm mai rapid pentru a determina când două grafice sunt la fel. Lucrarea din 2015, de László Babai de la Universitatea din Chicago, a spart o barieră importantă a vitezei de calcul, dar nu a ajuns la alta.

Acum, o lucrare de Xiaorui Sun de la Universitatea din Illinois, Chicago a prezentat un algoritm nou, mai rapid pentru o întrebare înrudită numită problema izomorfismului de grup, care se referă la a ști când două obiecte matematice numite grupuri sunt la fel. Lucrarea, postată online martie trecut, face un pas mic spre clarificarea complexității computaționale subiacente implicate în compararea obiectelor.

Lucrarea lui Sun încalcă o limită de viteză de lungă durată pentru o anumită clasă de grupuri - cea considerată cea mai dificilă instanță a problemei izomorfismului de grup de rezolvat. Dacă un algoritm poate compara rapid grupuri de acest fel, speranța este că poate compara rapid grupuri de orice tip.

„Nu cunoaștem o astfel de teoremă, dar avem motive să credem că așa ceva ar trebui să fie adevărat”, a spus Josh Grochow de la Universitatea Colorado, Boulder.

Compararea comparațiilor

Pentru a determina dacă două lucruri sunt identice într-un mod precis, mai întâi trebuie să definiți „la fel”. Două șiruri de numere ar putea fi considerate la fel dacă conțin doar aceleași cifre sau ar putea fi necesar să aibă aceleași cifre în aceeași ordine.

Izomorfismul este un anumit tip de asemănare care apare mult în matematică. Când două obiecte sunt izomorfe unul față de celălalt, înseamnă aproximativ că ele conțin aceleași elemente și că acele elemente sunt în aceeași relație unul cu celălalt.

Graficele — colecții de vârfuri (puncte) legate prin margini (linii) — oferă o modalitate accesibilă, vizuală, de a vedea cum poate arăta izomorfismul. Două grafice sunt izomorfe dacă puteți potrivi vârfurile dintr-un graf cu vârfurile din celălalt, astfel încât vârfurile care sunt conectate printr-o muchie în primul graf sunt conectate printr-o muchie în al doilea. Graficele izomorfe pot arăta diferit la suprafață, dar au o structură subiacentă.

Grupurile sunt mai abstracte decât graficele, dar încă pot fi comparate prin izomorfism. Un grup este o colecție de elemente - cum ar fi numere - care pot fi combinate între ele în funcție de o anumită operație, astfel încât rezultatul să fie și în colecție. De exemplu, puteți avea un grup ale cărui elemente sunt numere întregi — toate numerele întregi pozitive și negative, plus zero — și a cărui operație este adunarea: Adăugați oricare două numere întregi, iar rezultatul este întotdeauna un alt întreg.

Două grupuri sunt izomorfe dacă puteți împerechea fiecare element dintr-un grup cu un element din celălalt, astfel încât rezultatul operațiunii pe două elemente din primul grup să fie consecvent cu rezultatul operațiunii pe valorile echivalente ale acelor elemente în al doilea. grup.

Iată un exemplu simplu de două grupuri, fiecare cu două elemente, care sunt izomorfe unul față de celălalt. Primul grup este format din numerele 0 și 1, iar al doilea grup este format din litere a și b. Ambele grupuri conțin o operație de combinare a elementelor grupului într-un mod specific, cu rezultatele prezentate în tabelele de mai jos.

Grupurile sunt izomorfe deoarece 0 perechi cu a, 1 perechi cu b, iar relația structurală produsă prin combinarea elementelor este aceeași în ambele grupuri.

„Spunem că două grupuri sunt izomorfe dacă sunt practic echivalente”, a spus Sun.

Progres dezechilibrat

Izomorfismul este un concept important în matematică - în care graficele și grupurile sunt prezente pe scară largă - deoarece le permite matematicienilor să privească dincolo de diferențele superficiale și să se concentreze asupra modurilor în care obiectele înrudite pot fi de fapt aceleași. Dar este fundamental și în informatică; Cercetătorii nu caută doar algoritmi care determină dacă două obiecte sunt izomorfe, dar măsoară și cât de repede pot rula acești algoritmi.

Această măsurătoare poate fi dificilă. Viteza unui algoritm se bazează pe modul în care timpul de execuție se modifică în funcție de dimensiunea obiectelor la care lucrează. Imaginați-vă, de exemplu, că aveți două perechi de grupuri. Într-o pereche, fiecare grup conține cinci elemente. În celălalt, fiecare grup conține 10 elemente.

Te-ai aștepta să ia mai mult timp unui algoritm pentru a determina dacă grupurile cu mai multe elemente sunt izomorfe. Dar cât timp mai mult? Va dura de două ori mai mult? 5² mai lung? 2⁵ mai lung? Aceste întrebări corespund unor clasificări ample importante ale vitezei algoritmice: pot rula în timp liniar (ceea ce înseamnă că, în acest caz, durează de două ori mai mult), timp polinom (5² mai lung) și timp exponențial (2⁵ mai lung).

Informaticii știu în ce categorie de viteză se încadrează majoritatea întrebărilor de calcul, dar nu toate.

„Majoritatea sunt fie cele mai simple, fie cele mai dificile [tip de întrebare], dar există încă câteva excepții care sunt necunoscute”, a spus Sun. Izomorfismul de grafic și grup se numără printre aceste excepții, ceea ce le face atât de atractive pentru studiu.

În anii '1970, Robert Tarjan de la Universitatea Princeton a realizat că există un algoritm care poate determina dacă oricare două grupuri sunt izomorfe cu un timp de rulare de $latex n^{{(log,n)}}$, unde n este numărul de elemente din fiecare grupă. Acesta se numește algoritm de timp cvasi-polinom, iar în ierarhia timpilor de execuție este mai bine decât timpul exponențial (2ⁿ) dar mai rău decât timpul polinom (n²). Aceasta este aproximativ aceeași viteză ca algoritmul de izomorfism grafic al lui Babai și este încă cel mai bun lucru pe care îl putem face pentru grupuri aproape 50 de ani mai târziu.

„Aproximativ înseamnă că nu s-a înregistrat niciun progres timp de o jumătate de secol”, a spus Sun.

La momentul rezultatului lui Tarjan, problema izomorfismului de grup a fost studiată mai pe larg decât versiunea grafică. Acest lucru este inversat astăzi, în parte pentru că izomorfismul grafic a stimulat inovații interesante, în timp ce izomorfismul de grup a stagnat.

„Toate instrumentele noastre au fost foarte lente de ani de zile și a fost greu să exploatem ceea ce știm despre algebra [a grupurilor]”, a spus James Wilson de la Universitatea de Stat din Colorado.

Dar, în ciuda acestei disparități în curs, cele două probleme au o legătură mai profundă decât asemănarea numelor lor: Problema izomorfismului de grup (cel puțin în această formulare) se reduce la problema izomorfismului de graf. Aceasta înseamnă că orice algoritm care poate rezolva problema graficului poate rezolva și problema grupului într-o perioadă similară de timp. Reversul nu este adevărat - progresul pe grup nu implică progres pe grafic. Dar lipsa de progrese în problema grupului a cântărit matematicienii care caută câștiguri proporționale în problema graficului. Cum poți realiza un lucru mai greu dacă nu poți realiza mai întâi ceva care este strâns legat și pare și mai ușor?

„Cu alte cuvinte”, a spus Sun, „pentru a îmbunătăți și mai mult izomorfismul graficului, izomorfismul de grup este un mare blocaj.”

O problemă transformată

Când progresul asupra unei probleme se blochează la fel de mult ca pentru izomorfismul de grup, invenția este de obicei necesară pentru a se debloca. „Când aveți un avans mare, acesta ar trebui să fie un indiciu că există o idee nouă”, a spus Grochow.

Lucrarea lui Sun conține câteva idei care implică vizarea unui tip important de grup și găsirea unei modalități inteligente de a sparge acele grupuri în bucăți pentru a le compara.

Sunt numite grupurile pentru care lucrează algoritmul lui Sun p-grupe de clasa 2 si exponent p. Sunt similare cu grupurile în care produsul a două elemente este un alt element și produsul rămâne același indiferent de ordinea în care le înmulți. Dar ceea ce contează cu adevărat este ceea ce reprezintă ele pentru problema generală a izomorfismului de grup. Aceste grupuri au o structură foarte simplă, ceea ce înseamnă că ar trebui să fie ușor de comparat. Dar, în ciuda acestei simplități, cercetătorii nu găsiseră o modalitate de a accelera algoritmul. Până când au putut, sa simțit fără speranță să facă îmbunătățiri pentru problema generală a izomorfismului de grup.

Sun a început prin a comuta setarea de la grupuri la matrice, rețele de numere care servesc ca obiecte fundamentale în algebra liniară. Acest lucru a fost posibil datorită unei teoreme din anii 1930 numită corespondența Baer, ​​care transformă această versiune a întrebării izomorfismului de grup într-o problemă perfect analogă despre matrice. În special, Sun a lucrat cu spații matrice, care sunt colecții de matrice cu o proprietate specială: combinația (liniară) a oricăror două matrice din spațiu este egală cu o altă matrice din spațiu.

Cu alte cuvinte, aceste spații sunt structurate mult ca grupuri. Deci, în loc să încerce să înțeleagă când două grupuri sunt izomorfe, Sun ar putea încerca doar să înțeleagă când două spații matriceale sunt izometrice - o noțiune de izomorfism a spațiilor matriceale care corespunde cu cea a grupurilor.

Sun nu a fost primul cercetător care a adoptat această abordare, dar a fost primul care a introdus un pas suplimentar: împărțirea spațiului matriceal în două bucăți. O singură bucată este nucleul spațiului, în care toate matricele sunt simple. Cealaltă piesă este spațiul care înconjoară acel nucleu, în care toate matricele sunt deosebit de complexe. Această mișcare corespunde împărțirii unui grup în subgrupuri care conțin doar unele dintre elementele totale.

Sun a aplicat apoi diferite metode algoritmice pentru fiecare dintre aceste piese. Miezul are o structură simplă, așa că a folosit o caracterizare a structurii pentru a o reprezenta într-un mod mai organizat. Stratul exterior este mai complex, așa că nu există o modalitate evidentă rapidă de a-l compara cu altul. În schimb, metoda lui Sun adoptă o abordare numită individualizare și rafinare pentru a exclude majoritatea modalităților posibile de mapare a unui strat exterior pe celălalt și apoi utilizează un computer pentru a analiza toate modalitățile posibile rămase pentru a determina dacă există o potrivire izomorfă.

Metoda este similară în spirit cu modul în care ați putea rezolva un puzzle sudoku. Există unele pătrate ale căror valori potențiale sunt limitate de ceea ce știți deja (nucleul spațiului matricei), permițându-vă să le completați rapid. Apoi mai sunt și altele (stratul exterior) care au mai puține constrângeri, dar pe care le poți da seama doar încercând toate valorile posibile - și atâta timp cât nu sunt prea multe dintre aceste tipuri de pătrate, poți totuși să rezolvi puzzle-ul în o perioadă rezonabilă de timp.

„Completez toate lucrurile pe care le pot spune rapid că sunt restrictive, iar acum s-ar putea să mă întorc și să-mi încerc cu inima cu privire la cutiile lipsă”, a spus Wilson. „Dacă ai restrâns domeniul de aplicare, acum este un moment bun să schimbi vitezele și să folosești computerul pentru a căuta valorile potrivite.”

Descoperirea lui Sun a arătat că este întotdeauna posibil să se facă această împărțire pentru spațiile matriceale corespunzătoare p-grupe de clasa 2 si exponent p. Apoi a demonstrat că, după o astfel de împărțire, o combinație de tehnici algoritmice face posibilă determinarea dacă două spații sunt izomorfe în $latex n^{{(log,n)}^{5/6}}$ timp, o valoare care este puțin mai mică decât metoda $latex n^{{(log,n)}}$ a lui Tarjan. (Ambele algoritmi includ, de asemenea, termeni constanți, care nu au un efect mare asupra timpului de execuție și pe care i-am omis pentru claritate.)

Rezultatul nu determină în ce categorie de viteză se încadrează izomorfismul grupului; este încă undeva între timpul exponențial și cel polinomial. Dar Soarele l-a îndreptat puțin mai aproape de partea polinomială a lucrurilor și există motive să credem că ar fi posibil mai mult decât atât. La urma urmei, munca sa le oferă informaticienilor un algoritm de izomorfism de grup mai rapid pentru cele mai dificile tipuri de grupuri, ridicând posibilitatea ca o accelerare similară să fie la îndemână pentru grupuri de toate tipurile.

„Dacă o poți rezolva pentru p-grupuri, probabil că puteți rezolva totul”, a spus Grochow. "Pot fi."