Egy könnyen hangzó probléma túl nagy számokat eredményez az univerzumunk számára | Quanta Magazin

Nem gyakran fordul elő, hogy az 5 évesek felfogják a számítástechnika határterületein felmerülő kérdéseket, de előfordulhat. Tegyük fel például, hogy egy Alice nevű óvodásnak van két almája, de ő jobban szereti a narancsot. Szerencsére az osztálytársai egészséges gyümölcskereskedelmi rendszert alakítottak ki szigorúan bevezetett árfolyamokkal: mondjuk lemond egy almáról, és kaphat egy banánt. Képes-e Alice egy sor kereskedést végrehajtani banán vagy sárgadinnye felszedésével és kirakodásával, amivel eljut kedvenc gyümölcséhez?

Elég egyszerűen hangzik. „Mehetsz általános iskolába, és elmondhatod a gyerekeknek” – mondta Christoph Haase, az Oxfordi Egyetem informatikusa. "Az emberek azt fogják gondolni: "Ez könnyű lehet."

De az Alice dilemmája mögött meghúzódó matematikai probléma – amelyet vektorösszeadási rendszerek elérhetőségi problémájának neveznek – meglepően finom. Míg egyes esetek könnyen megoldhatók, az informatikusok közel fél évszázadon át küzdöttek a probléma átfogó megértése érdekében. Most, az elmúlt néhány évben történt áttörések sorozata során, határozottan megállapították, hogy ez a probléma milyen bonyolulttá válhat.

Kiderült, hogy ez a gyermeki probléma abszurd, szinte karikatúraszerűen összetett – olyan összetett, mint gyakorlatilag az összes többi híresen nehéz számítási problémák gyerekjátéknak néz ki. Próbálja számszerűsíteni a probléma megoldásához szükséges erőfeszítéseket, és hamarosan olyan nagy számokkal kell szembenéznie, hogy még a számjegyeik megszámlálásával is olyan számokhoz nyúlhat, amelyekről még soha nem hallott. Az ilyen számok gyakran az univerzum léptékével való összehasonlítást tesznek lehetővé, de még ezek az analógiák is elmaradnak. „Ez nem tenné igazságot” – mondta Georg Zetzsche, informatikus a Max Planck Szoftverrendszerek Intézetében, Kaiserslauternben, Németországban. "Olyan kicsi az univerzum."

Karnyújtásnyira?

Lényegére lecsupaszítva az elérhetőségi probléma a vektoroknak nevezett matematikai objektumokra vonatkozik, amelyek számok rendezett listái. Az ezekben a listákban szereplő bejegyzéseket komponenseknek, a vektorban lévő komponensek számát pedig dimenziójának nevezzük. Alice gyümölcskészlete például leírható egy négydimenziós vektorral (a, b, c, d), amelynek összetevői azt jelzik, hogy adott időpontban hány almája, banánja, sárgadinnye és narancsa van.

A vektorösszeadási rendszer vagy VAS olyan vektorok gyűjteménye, amelyek a rendszer állapotai közötti lehetséges átmeneteket reprezentálják. Alice esetében az átmeneti vektor (-1, -1, 1, 0) egy alma és egy banán sárgadinnyére cseréjét jelentené. A VAS elérhetőségi problémája azt kérdezi, hogy létezik-e olyan engedélyezett átmenet-kombináció, amely egy adott kezdeti állapotból egy adott célállapotba vihet át – vagy, matematikai értelemben, van-e olyan átmeneti vektorok összege, amelyek a kezdővektort a célvektorrá alakítják át. Csak egy fogás van: a rendszer állapotát leíró vektor egyetlen komponense sem süllyedhet nulla alá.

„Ez egy nagyon természetes korlátozás a valóságmodell számára” – mondta Wojciech Czerwiński, a Varsói Egyetem informatikusa. "Nem lehet negatív számú alma."

Egyes rendszerekben könnyű meghatározni, hogy a célvektor elérhető-e. De ez nem mindig van így. Az informatikusokat leginkább az egyszerű megjelenésű vektorösszeadási rendszerek érdeklik, amelyekben nem nyilvánvaló, mennyire nehéz meghatározni az elérhetőséget. Az esetek tanulmányozásához a kutatók egy szám meghatározásával kezdik, amely számszerűsíti egy adott rendszer méretét. Ezt a számot képviseli n, magában foglalja a dimenziók számát, az átmenetek számát és egyéb tényezőket. Ezután megkérdezik, hogy milyen gyorsan nőhet az elérhetőségi probléma nehézsége n nagyobbra nő.

A kérdés megválaszolására a kutatók két egymást kiegészítő megközelítést alkalmaznak. Először is olyan különösen trükkös vektorösszeadási rendszerekre keresnek példákat, amelyekben az elérhetőség meghatározása minimális erőfeszítést igényel. Ezeket a minimális szinteket a probléma összetettségének „alsó határainak” nevezik – a kutatóknak azt mondják: „A legtrükkösebb rendszerek egy adott esetre n legalább ilyen nehezek."

Másodszor, a kutatók megpróbálják felállítani a „felső határokat” – korlátokat annak, hogy milyen nehéz lehet az elérhetőség, még a legördögibb rendszerekben is. Ezek azt mondják: „A legbonyolultabb esetek adott adottsághoz n legfeljebb ilyen nehezek." Annak meghatározására, hogy a legnehezebb rendszerekben mennyire nehéz az elérhetőség, a kutatók megpróbálják az alsó határokat felfelé, a felső határokat lefelé tolni, amíg találkoznak.

A rémálmok dolga

A vektorösszeadási rendszerek hosszú múltra tekintenek vissza. Az 1960-as évek óta az informatikusok olyan programok modellezésére használták őket, amelyek a számításokat sok kis darabra bontják, és egyidejűleg dolgoznak ezeken a darabokon. Ez a fajta „párhuzamos számítástechnika” ma már mindenütt elterjedt, de a kutatók még mindig nem értik teljesen annak matematikai alapjait.

1976-ben az informatikus Richard Lipton megtette az első lépést a VAS elérhetőségi probléma összetettségének megértése felé. Eljárást dolgozott ki rendszerek felépítésére, amelyben a leggyorsabb módja annak meghatározásának, hogy az egyik állapot elérhető-e a másikból, ha feltérképezi a köztük lévő átmenetek sorozatát. Ez lehetővé tette számára, hogy a két gondosan kiválasztott állapot közötti legrövidebb út hosszát használja az elérhetőségi probléma nehézségének mérésére.

Akkor Lipton bizonyított méretrendszert tudott felépíteni n amelyben a két állapot közötti legrövidebb út több mint $latex 2^{2^n}$ átmenetet tartalmazott. Ez megfelelő kétszeres exponenciális alsó korlátot jelentett a rendszerében elérhető elérhetőség meghatározásához szükséges erőfeszítésekre. Megdöbbentő felfedezés volt – a dupla exponenciális növekedés az informatikusok rémálmai közé tartozik. Valójában a kutatók gyakran megtagadják a szokásos exponenciális növekedést is, ami elhalványul a viszonylatban: $latex {2^5}= 32 $, de a $latex 2^{2^5} $ több mint 4 milliárd.

A legtöbb kutató úgy gondolta, hogy Lipton a lehető legbonyolultabb vektorösszeadási rendszert dolgozta ki, ami azt jelenti, hogy az alsó határt olyan magasra emelte, amennyire csak lehetett. Ebben az esetben csak egy felső határ hiányozna, vagyis annak bizonyítéka, hogy nem létezhet olyan rendszer, amelyben még nehezebb lenne meghatározni az elérhetőséget. De ezt senki sem tudta, hogyan bizonyítsa be. Ernst Mayr informatikus jött a legközelebb, amikor ő bizonyított 1981-ben, hogy elvileg mindig meg lehet határozni az elérhetőséget bármely vektorösszeadási rendszerben. De a bizonyítása nem szabott mennyiségi felső határt arra vonatkozóan, hogy milyen nehéz lehet a probléma. Volt padló, de mennyezet nem látszott.

„Mindenképpen gondolkodtam rajta ki- és bekapcsolva” – mondta Lipton. "De egy idő után feladtam, és amennyire meg tudtam állapítani, senki sem haladt előre körülbelül 40 évig."

2015-ben az informatikusok Jérôme Leroux és a Sylvain Schmitz végre létrejött mennyiségi felső határ - olyan magas, hogy a kutatók azt feltételezték, hogy ez csak az első lépés, amelyet le lehet tolni, hogy elérje Lipton alsó határát.

De nem ez történt. 2019-ben a kutatók egy Liptonnál jóval magasabb alsó határt fedeztek fel, ami több évtizedes hagyományos bölcsesség felborulása. A VAS elérhetőségi problémája sokkal összetettebb volt, mint azt bárki gondolta volna.

Az erők tornya

A 2019-es megdöbbentő eredmény a kudarcból nőtt ki. 2018-ban Czerwiński megcáfolt egy sejtést, Leroux és Filip Mazowiecki, aki jelenleg a Varsói Egyetem informatikusa, ez segített volna előrelépést elérni egy kapcsolódó probléma megoldásában. A későbbi megbeszélések során a kutatók egy ígéretes új módot találtak az extra-komplex vektorösszeadási rendszerek felépítésére, ami új alsó korlátot jelenthet a VAS elérhetőségi problémájában, ahol a fejlődés oly sokáig megakadt.

„Minden a VAS elérhetőségével függött össze a fejemben” – emlékezett vissza Czerwiński. Egy kis tanítási terhelésű félév során úgy döntött, hogy Leroux-val, Mazowieckivel és két másik kutatóval együtt kizárólag erre a problémára összpontosít – Sławomir Lasota a Varsói Egyetem és Ranko Lazić a Warwicki Egyetem tanára.

Néhány hónap elteltével erőfeszítéseik meghozták gyümölcsüket. Czerwiński és kollégái igazolták hogy olyan vektorösszeadási rendszereket tudtak felépíteni, amelyekben a két állapot közötti legrövidebb utat a rendszer méretéhez hozták a tetraciónak nevezett matematikai művelettel, amely még a rémálomszerű kettős exponenciális növekedést is szelídnek tűnik.

A tetráció a matematika legismertebb műveleteit összekötő minta egyenes kiterjesztése, az összeadástól kezdve. Adjuk össze n egy szám másolatát, és az eredmény megegyezik a szám szorzatával n. Ha együtt szorozod n egy szám másolata, ami egyenértékű a hatványozással, vagy a szám értékre emelésével nth hatalom. A tetrálás, amelyet gyakran felfelé mutató nyílpár képvisel, a következő lépés ebben a sorozatban: Egy szám tetrálása n hatványozását jelenti n idők, hogy erőtornyot hozzanak létre n emeletek magas.

Nehéz felfogni, milyen gyorsan megy ki a tetrálás: a $latex 2 uparrowuparrow 3$ vagy a $latex 2^{2^2}$ 16, a $latex 2 uparrowuparrow 4$ valamivel több, mint 65,000 2, és $latex 5 uparrowuparrow 20,000$ egy közel 2 6 számjegyből álló szám. Fizikailag lehetetlen leírni a $latex XNUMX uparrowuparrow XNUMX$ összes számjegyét – ez egy ilyen kis univerzumban való élet felelőssége.

Czerwiński és munkatársai mérföldkőnek számító eredményükben bebizonyították, hogy léteznek nagy méretű vektorösszeadási rendszerek n ahol az elérhetőség meghatározásának legjobb módja egy olyan útvonal feltérképezése, amely több mint $latex 2 uparrowuparrow n$ átmenetet tartalmaz, ami egy új alsó korlátot jelent, amely eltörpül Liptoné mellett. De bármennyire is fejforgató a tetráció, még mindig nem ez volt a végső szó a probléma összetettségéről.

Quinquagintillion és túl 

Alig néhány hónappal a VAS elérhetőségének összetettségének megdöbbentő új alsó határa után Leroux és Schmitz lenyomott a felső határt, amelyet három évvel korábban megállapítottak, de nem jutottak el egészen a tetracióig. Ehelyett bebizonyították, hogy az elérhetőségi probléma összetettsége nem nőhet gyorsabban, mint az Ackermann-függvénynek nevezett matematikai szörnyűség.

Ennek a függvénynek a megértéséhez vigye a tetració meghatározásához használt mintát a komor következtetésig. A sorozat következő művelete, az úgynevezett pentáció, ismételt tetraciót jelent; ezt egy újabb művelet (hexáció) követi az ismételt pentációhoz, és így tovább.

Az Ackermann-függvény, amelyet $latex A(n)$ jelöléssel kapunk, ha egy lépéssel feljebb lépünk ezen a műveleti létrán a számegyenes minden egyes megállásával: $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}}$, és így tovább. A $latex A(4)$ számjegyeinek száma maga is egy kolosszális szám, amely megközelítőleg egyenlő 1 kvinkvagintilillióval – ez a szeszélyes és ritkán szükséges neve egy 1-nek, amelyet 153 nulla követ. „Ne aggódjon az 5 éves Ackermann miatt” – tanácsolta Javier Esparza, a Müncheni Műszaki Egyetem informatikusa.

Leroux és Schmitz eredménye nagy rést hagyott az alsó és a felső határ között – a VAS elérhetőségi problémájának pontos összetettsége a tartomány bármelyik végén vagy a kettő között lehet. Czerwiński nem akarta hagyni ezt a különbséget. „Továbbra is dolgoztunk ezen, mert egyértelmű volt, hogy ez a legnagyobb dolog, amit életünkben tettünk” – mondta.

A végső áttörést 2021-ben érte el, miközben Czerwiński egy Łukasz Orlikowski nevű másodéves egyetemi hallgatónak adott tanácsot. A probléma egyszerű változatát rendelte Orlikowskihoz, hogy felgyorsítsa, és Orlikowski munkája segítette kettejüket egy új technika kidolgozásában, amely az általános elérhetőségi problémára is vonatkozik. Ez lehetővé tette számukra emelje fel az alsó határt lényegében – egészen Leroux és Schmitz Ackermann felső határáig. Leroux önállóan dolgozott egyenértékű eredmény körülbelül ugyanabban az időben.

Végül a kutatók feltárták az elérhetőségi probléma valódi összetettségét. Czerwiński, Orlikowski és Leroux alsó korlátja megmutatta, hogy van egy fokozatosan nagyobb vektorösszeadási rendszer sorozata, amelyben a két állapot közötti legrövidebb út az Ackermann-függvénnyel arányosan növekszik. Leroux és Schmitz felső korlátja megmutatta, hogy az elérhetőségi probléma nem lehet ennél bonyolultabb – kevés vigasz annak, aki egy csalhatatlan gyakorlati eljárásban reménykedik a megoldására. Feltűnően szemlélteti, hogy a látszólag egyszerű számítási problémák milyen finomak lehetnek.

Soha nem fejeződött be

A kutatók folytatták a VAS elérhetőségi problémájának tanulmányozását, miután meghatározták annak pontos összetettségét, mivel a kérdés számos változata megválaszolatlan maradt. Az Ackermann felső és alsó határ például nem tesz különbséget a növekedés különböző módjai között n, mint például a vektorok dimenziósságának növelése vagy a megengedett átmenetek számának növelése.

A közelmúltban Czerwiński és kollégái haladást ért el ezeknek az eltérő hatásoknak a szétszedése annak tanulmányozásával, hogy milyen gyorsan nőhet a komplexitás a rögzített dimenziójú vektorösszeadási rendszerek változataiban. De még több a tennivaló – még három dimenzióban is, ahol a vektorösszeadási rendszereket könnyű megjeleníteni, az elérhetőségi probléma pontos összetettsége továbbra is ismeretlen.

„Bizonyos értelemben ez kínos számunkra” – mondta Mazowiecki.

A kutatók azt remélik, hogy a viszonylag egyszerű esetek jobb megértése segít új eszközöket kifejleszteni más számítási modellek tanulmányozására, amelyek bonyolultabbak, mint a vektorösszeadási rendszerek. Jelenleg szinte semmit sem tudunk ezekről a bonyolultabb modellekről.

„Ezt a kiszámíthatóság megértésére irányuló alapvető törekvés részének tekintem” – mondta Zetzsche.

Quanta felméréssorozatot végez közönségünk jobb kiszolgálása érdekében. Vidd a miénket számítástechnikai olvasói felmérés és ingyenesen nyerhetsz Quanta áru.