O problemă care sună ușor dă numere prea mari pentru universul nostru | Revista Quanta

Nu se întâmplă adesea ca copiii de 5 ani să înțeleagă întrebări la frontierele informaticii, dar se poate întâmpla. Să presupunem, de exemplu, că o grădiniță pe nume Alice are două mere, dar ea preferă portocalele. Din fericire, colegii ei de clasă au dezvoltat un sistem sănătos de comercializare a fructelor, cu rate de schimb strict impuse: renunță la un măr, să zicem, și poți obține o banană. Poate Alice să execute o serie de tranzacții, prin ridicarea și descărcarea de banane sau pepeni galbeni, care o duc la fructul ei preferat?

Sună destul de simplu. „Poți să mergi la școala primară și să le spui copiilor”, a spus Christoph Haase, un informatician la Universitatea din Oxford. „Oamenii se vor gândi: „Trebuie să fie ușor.””

Dar problema de matematică care stă la baza dilemei lui Alice - numită problema accesibilității pentru sistemele de adunare vectorială - este surprinzător de subtilă. În timp ce unele cazuri pot fi rezolvate cu ușurință, informaticienii s-au luptat timp de aproape jumătate de secol pentru a dezvolta o înțelegere cuprinzătoare a problemei. Acum, într-o serie de descoperiri din ultimii câțiva ani, au stabilit cu fermitate cât de complexă poate deveni acea problemă.

Se pare că această problemă copilărească este absurd, aproape de caricatură complexă - atât de complexă încât practic toate celelalte renumite probleme de calcul dificile arata ca, ei bine, o joaca de copii. Încercați să cuantificați efortul necesar pentru a rezolva această problemă și, în curând, vă veți confrunta cu numere atât de mari încât chiar și numărând cifrele lor vă va face să ajungeți la numere despre care nu ați auzit niciodată. Asemenea numere invită adesea la comparații cu scara universului, dar chiar și acele analogii nu se potrivesc. „Asta nu i-ar face dreptate”, a spus Georg Zetzsche, un informatician la Institutul Max Planck pentru Sisteme Software din Kaiserslautern, Germania. „Universul este atât de mic.”

In proximitate?

Dezbrăcat la esență, problema accesibilității este despre obiecte matematice numite vectori, care sunt liste ordonate de numere. Intrările din aceste liste se numesc componente, iar numărul de componente dintr-un vector se numește dimensionalitate. Inventarul de fructe al lui Alice, de exemplu, poate fi descris printr-un vector cu patru dimensiuni (a, b, c, d), ale căror componente reprezintă câte mere, banane, pepeni galbeni și portocale are la un moment dat.

Un sistem de adiție vectorială, sau VAS, este o colecție de vectori care reprezintă posibilele tranziții între stările dintr-un sistem. Pentru Alice, vectorul de tranziție (−1, −1, 1, 0) ar reprezenta schimbul unui măr și o banană cu un pepene galben. Problema accesibilității VAS întreabă dacă există vreo combinație de tranziții permise care vă poate duce de la o anumită stare inițială la o anumită stare țintă - sau, în termeni matematici, dacă există vreo sumă de vectori de tranziție care transformă vectorul de pornire în vectorul țintă. Există o singură captură: nicio componentă a vectorului care descrie starea sistemului nu poate scădea vreodată sub zero.

„Aceasta este o restricție foarte naturală pentru un model de realitate”, a spus Wojciech Czerwiński, un informatician la Universitatea din Varșovia. „Nu poți avea un număr negativ de mere.”

În unele sisteme, este ușor să determinați dacă vectorul țintă este accesibil. Dar nu este întotdeauna cazul. Informaticii sunt cei mai interesați de sistemele simple de adăugare a vectorilor, în care nu este evident cât de greu este să se determine accesibilitatea. Pentru a studia aceste cazuri, cercetătorii încep prin a defini un număr care cuantifică dimensiunea unui sistem dat. Acest număr, reprezentat de n, cuprinde numărul de dimensiuni, numărul de tranziții și alți factori. Apoi se întreabă cât de repede poate crește dificultatea problemei de accesibilitate n creste mai mare.

Pentru a răspunde la această întrebare, cercetătorii folosesc două abordări complementare. În primul rând, ei caută exemple de sisteme de adiție vectorială deosebit de complicate în care determinarea accesibilității necesită un nivel minim de efort. Aceste niveluri minime sunt numite „limite inferioare” ale complexității problemei – ei spun cercetătorilor: „Cele mai complicate sisteme pentru un anumit n sunt cel puțin atât de grei.”

În al doilea rând, cercetătorii încearcă să stabilească „limite superioare” – limite ale cât de greu poate ajunge accesibilitatea, chiar și în cele mai diabolice sisteme. Acestea spun: „Cele mai dificile cazuri pentru un dat n sunt cel mult atât de grei.” Pentru a determina cu exactitate cât de greu este accesibilitatea în sistemele cele mai dificile, cercetătorii încearcă să împingă limitele inferioare în sus și limitele superioare în jos până când se întâlnesc.

Lucrurile coșmarurilor

Sistemele de adiție vectorială au o istorie lungă. Din anii 1960, informaticienii le-au folosit pentru a modela programe care descompun un calcul în multe bucăți mici și lucrează la acele piese simultan. Acest tip de „calculatură concomitentă” este acum omniprezentă, dar cercetătorii încă nu înțeleg pe deplin fundamentele sale matematice.

În 1976, informaticianul Richard Lipton a făcut primul pas spre înțelegerea complexității problemei de accesibilitate a VAS. El a dezvoltat o procedură pentru construirea de sisteme în care cea mai rapidă modalitate de a determina dacă o stare este accesibilă dintr-o altă stare este de a mapa o secvență de tranziții între ele. Acest lucru i-a permis să folosească lungimea drumului cel mai scurt dintre două stări alese cu grijă ca măsură a dificultății problemei de accesibilitate.

Lipton atunci s-au dovedit el ar putea construi un sistem de dimensiuni n în care calea cea mai scurtă între două stări implica mai mult de $latex 2^{2^n}$ tranziții. Aceasta a implicat o limită inferioară dublă exponențială corespunzătoare a efortului necesar pentru a determina accesibilitatea în sistemele sale. A fost o descoperire uluitoare – creșterea dublă exponențială este chestia coșmarurilor informaticienilor. Într-adevăr, cercetătorii se opun adesea chiar și la creșterea exponențială obișnuită, care palidează în comparație: $latex {2^5}= 32$, dar $latex 2^{2^5}$ este de peste 4 miliarde.

Majoritatea cercetătorilor au crezut că Lipton a pregătit cele mai complexe sisteme de adiție vectorială posibile, ceea ce înseamnă că a ridicat limita inferioară cât putea de sus. Singurul lucru care lipsește, în acest caz, ar fi o limită superioară pentru a merge cu ea - adică o dovadă că nu ar putea exista un sistem în care determinarea accesibilității să fie și mai dificilă. Dar nimeni nu a știut cum să demonstreze asta. Informaticianul Ernst Mayr s-a apropiat cel mai mult când el s-au dovedit în 1981 că este întotdeauna posibil, în principiu, să se determine accesibilitatea în orice sistem de adiție vectorială. Dar dovada lui nu a pus nicio limită cantitativă superioară asupra cât de grea ar putea fi problema. Era un podea, dar nu se vedea niciun tavan.

„Cu siguranță m-am gândit la asta din când în când”, a spus Lipton. „Dar după un timp am renunțat și, din câte mi-am dat seama, nimeni nu a făcut niciun progres timp de 40 de ani.”

În 2015, informaticienii Jérôme Leroux și Sylvain Schmitz stabilit în cele din urmă o limită superioară cantitativă — unul atât de mare încât cercetătorii au presupus că este doar un prim pas care ar putea fi împins în jos pentru a atinge limita inferioară a lui Lipton.

Dar nu asta sa întâmplat. În 2019, cercetătorii au descoperit o limită inferioară mult mai mare decât cea a lui Lipton, schimbând decenii de înțelepciune convențională. Problema accesibilității VAS era mult mai complexă decât anticipase oricine.

Un turn al puterilor

Rezultatul șocant din 2019 a apărut din eșec. În 2018, Czerwiński a infirmat o presupunere a lui Leroux și Filip Mazowiecki, un informatician acum la Universitatea din Varșovia, care ar fi ajutat la progrese în privința unei probleme conexe. În discuțiile ulterioare, cercetătorii au găsit o nouă modalitate promițătoare de a construi sisteme de adiție vectorială extra-complexă, care ar putea implica o nouă limită inferioară a problemei de accesibilitate a VAS, unde progresul s-a blocat atât de mult timp.

„Totul era legat în mintea mea de accesibilitatea VAS”, și-a amintit Czerwiński. Pe parcursul unui semestru cu o încărcătură ușoară de predare, el a decis să se concentreze exclusiv pe această problemă, împreună cu Leroux, Mazowiecki și alți doi cercetători — Sławomir Lasota al Universității din Varșovia și Ranko Lazić de la Universitatea din Warwick.

După câteva luni, eforturile lor au dat roade. Czerwiński și colegii săi demonstrat că ar putea construi sisteme de adiție vectorială în care calea cea mai scurtă dintre două stări era legată de dimensiunea sistemului printr-o operație matematică numită tetrație care face ca și creșterea exponențială dublă de coșmar să pară blândă.

Tetrarea este o extensie simplă a unui model care conectează cele mai familiare operații din matematică, începând cu adunarea. Adăugați împreună n copii ale unui număr, iar rezultatul este echivalent cu înmulțirea acelui număr cu n. Dacă vă înmulțiți împreună n copii ale unui număr, care este echivalent cu exponențiare sau cu creșterea numărului la nputerea. Tetrarea, adesea reprezentată de o pereche de săgeți îndreptate în sus, este următorul pas din această secvență: tetrarea unui număr prin n înseamnă a-l exponenția n ori pentru a produce un turn al puterilor n povești înalte.

Este greu să-ți înțelegi cât de repede tetrarea scapă de sub control: $latex 2 uparrowuparrow 3$, sau $latex 2^{2^2}$, este 16, $latex 2 uparrowuparrow 4$ este puțin peste 65,000 și $latex 2 uparrowuparrow 5$ este un număr cu aproape 20,000 de cifre. Este imposibil din punct de vedere fizic să notezi toate cifrele $latexului 2 uparrowuparrow 6$ — o obligație de a trăi într-un univers atât de mic.

În rezultatul lor de referință, Czerwiński și colegii săi au demonstrat că există sisteme de adiție vectorială de mărime n unde cel mai bun mod de a determina accesibilitatea este de a trasa o cale care implică mai mult de $latex 2 în sus, în sus n$ tranziții, implicând o nouă limită inferioară care o depășește pe cea a lui Lipton. Dar, oricât de captivantă este tetrarea, încă nu a fost ultimul cuvânt asupra complexității problemei.

La Quinquagintillion și Dincolo 

La doar câteva luni după noua limită inferioară șocantă a complexității accesibilității VAS, Leroux și Schmitz impins in jos limita superioară pe care o stabiliseră cu trei ani mai devreme, dar nu ajunseseră până la tetrare. În schimb, au demonstrat că complexitatea problemei de accesibilitate nu poate crește mai repede decât o monstruozitate matematică numită funcția Ackermann.

Pentru a înțelege această funcție, luați modelul folosit pentru a defini tetrarea la concluzia sa sumbră. Următoarea operație din secvență, numită pentație, reprezintă tetrarea repetată; este urmată de încă o operație (hexare) pentru pentație repetată și așa mai departe.

Funcția Ackermann, denumită $latex A(n)$, este ceea ce obții atunci când treci cu o treaptă în această scară de operații cu fiecare oprire pe linia numerică: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ și așa mai departe. Numărul de cifre din $latex A(4)$ este el însuși un număr colosal aproximativ egal cu 1 quinquagintillion - acesta este numele capricios și rar necesar pentru un 1 urmat de 153 de zerouri. „Nu vă faceți griji pentru Ackermann de 5”, a sfătuit Javier Esparza, un informatician la Universitatea Tehnică din München.

Rezultatul lui Leroux și Schmitz a lăsat un decalaj mare între limitele inferioare și superioare - complexitatea precisă a problemei de accesibilitate a VAS ar putea fi la fiecare capăt al intervalului sau oriunde între ele. Czerwiński nu a intenționat să lase acest decalaj să rămână. „Am continuat să lucrăm la asta pentru că era clar că este cel mai mare lucru pe care l-am făcut vreodată în viața noastră”, a spus el.

Descoperirea finală a avut loc în 2021, în timp ce Czerwiński îl sfătuia pe un student de licență în anul doi, pe nume Łukasz Orlikowski. El i-a atribuit lui Orlikowski o variantă simplă a problemei pentru a-l pune la curent, iar munca lui Orlikowski i-a ajutat pe cei doi să dezvolte o nouă tehnică care se aplică și problemei generale de accesibilitate. Asta le-a permis ridicați limita inferioară substanțial — până la limita superioară a lui Ackermann a lui Leroux și Schmitz. Lucrând independent, Leroux a obținut un rezultat echivalent cam in acelasi timp.

În cele din urmă, cercetătorii au stabilit adevărata complexitate a problemei de accesibilitate. Limita inferioară a lui Czerwiński, Orlikowski și Leroux a arătat că există o secvență de sisteme de adiție vectorială progresiv mai mare în care calea cea mai scurtă dintre două stări crește proporțional cu funcția Ackermann. Limita superioară a lui Leroux și Schmitz a arătat că problema accesibilității nu poate deveni mai complexă decât atât - puțină consolare pentru oricine care speră într-o procedură practică infailibilă pentru a o rezolva. Este o ilustrare izbitoare a cât de subtile pot fi problemele de calcul aparent simple.

Niciodată Terminat

Cercetătorii au continuat să studieze problema accesibilității VAS după ce i-au determinat complexitatea exactă, deoarece multe variante ale întrebării rămân fără răspuns. Limitele superioare și inferioare Ackermann, de exemplu, nu fac distincție între diferitele moduri de creștere n, precum creșterea dimensionalității vectorilor sau creșterea numărului de tranziții permise.

Recent, Czerwiński și colegii săi au a făcut progrese eliminând aceste efecte distincte prin studierea cât de repede poate crește complexitatea în variantele sistemelor de adiție vectorială cu dimensionalitate fixă. Dar mai rămân de făcut – chiar și în trei dimensiuni, unde sistemele de adiție vectorială sunt ușor de vizualizat, complexitatea exactă a problemei de accesibilitate rămâne necunoscută.

„Într-un fel, este doar jenant pentru noi”, a spus Mazowiecki.

Cercetătorii speră că o mai bună înțelegere a cazurilor relativ simple îi va ajuta să dezvolte noi instrumente pentru a studia alte modele de calcul care sunt mai elaborate decât sistemele de adiție vectorială. În prezent, nu știm aproape nimic despre aceste modele mai elaborate.

„Văd acest lucru ca parte a unei căutări fundamentale de a înțelege computabilitatea”, a spus Zetzsche.

Cuante efectuează o serie de sondaje pentru a servi mai bine publicul nostru. Ia-ne sondaj cititor de informatică și vei fi înscris pentru a câștiga gratuit Cuante mărfuri.