Cea mai mare descoperire în 30 de ani în matematica alocării echilibrate
Doi cercetători au îmbunătățit, pentru prima dată din 1998, limita teoretică a cât de dezechilibrată poate fi împărțirea unor obiecte între două grupuri, un rezultat abstract cu aplicații directe în optimizare și învățare automată.
Nikhil Bansal, de la Universitatea din Michigan, și Haotian Jiang, de la Universitatea din Chicago, împreună cu colaboratori precum Raghu Meka, au obținut o îmbunătățire majoră a unei probleme matematice deschise din anii 1980, cunoscută drept conjectura Komlós. Problema pare simplă: dacă împarți un set de obiecte, reprezentate ca vectori, între două grupuri, cât de dezechilibrate pot ajunge cele două grupuri, în cel mai rău caz posibil, indiferent de câte dimensiuni au obiectele?
Conjectura spune că dezechilibrul maxim rămâne mărginit de o constantă universală, oricât de complexe ar fi obiectele. Ultima îmbunătățire majoră a limitei superioare data din 1998, când s-a demonstrat că dezechilibrul nu poate depăși rădăcina pătrată din logaritmul lui N, unde N e numărul de obiecte.
Ce s-a schimbat
Noul rezultat coboară limita la rădăcina a patra din logaritmul lui N, o îmbunătățire care pare mică scrisă în formulă, dar e uriașă în practică. Pentru a ilustra diferența, autorii dau un exemplu concret: chiar dacă N ar fi cât numărul estimat de atomi din tot universul, adică 10 la puterea 81, valoarea maximă a dezechilibrului rezultată din noua limită e doar 3.
Daniel Spielman, de la Universitatea Yale, a rezumat sugestiv miza rezultatului: în toată viața, spune el, cineva nu va întâlni niciodată în practică un număr N pentru care rădăcina a patra din logaritmul lui N depășește 5. Bansal a descris intuiția din spatele demonstrației astfel: deși cele două probleme combinate în demonstrație par legate, se poate manevra între ele astfel încât să nu se încurce reciproc.
Dincolo de eleganța matematică, teoria discrepanței stă la baza unor probleme practice de alocare echilibrată a resurselor, cu aplicații menționate de cercetători în optimizarea operațiunilor, în sistemele de învățare automată și, mai recent, în arhitectura modelelor de limbaj de tip LLM, unde echilibrarea corectă a datelor sau a sarcinilor de calcul contează direct pentru eficiență.
E genul de reușită care nu produce un produs peste noapte, dar mută limita a ce se știe sigur despre o problemă fundamentală, deschisă de treizeci de ani, cu ecouri în domenii care depind de matematica din spatele lor mai mult decât pare la prima vedere.
Sursă: Quanta Magazine