Ez a klasszikus eredmény lehetővé tette, hogy bármely adott időkerettel rendelkező algoritmust átalakítsunk egy olyan új algoritmussá, amely kevesebb tárhelyet használ. Williams rájött, hogy egy „puha kavicsokon” alapuló szimulációval az új algoritmus tárhelyigénye jelentősen csökkenthető – nagyjából az eredeti algoritmus időkeretének négyzetgyökével egyenlő mértékben. Ez az új, tárhelykímélő algoritmus azonban sokkal lassabb lett volna, így gyakorlati alkalmazása nem volt valószínű. Elméleti szempontból viszont forradalminak számított.
50 éven át a kutatók azt hitték, hogy lehetetlen túlszárnyalni Hopcroft, Paul és Valiant univerzális szimulációs módszerét. Williams ötlete – ha működik – nemcsak megdöntötte volna a rekordot, hanem teljesen felülírta volna azt. „Gondoltam rá, és azt mondtam: ›Ez egyszerűen nem lehet igaz‹” – emlékezett Williams. Elhelyezte a fiókba, és csak egy júliusi napon tért vissza hozzá, amikor megpróbálta megtalálni a hibát az elméletben – de nem talált. Miután rájött, hogy nincs hiba, hónapokig dolgozott a bizonyítás tisztázásán.
Február végén Williams végül közzétette a kész cikket. Cook és Mertz ugyanolyan meglepettek voltak, mint mindenki más. „Hosszú sétára kellett mennem, mielőtt bármi mást csináltam volna” – mondta Mertz. Valiant már februárban, a reggeli utazása során betekintést kapott Williams fejlesztésébe, ami az ő évtizedes eredményét javította. Bár korábban is találkoztak, csak most tudták meg, hogy egy környéken laknak, amikor egy havas februári napon a buszon találkoztak. Williams elmagyarázta a bizonyítást a meglepett Valiantnak, aki lenyűgözve reagált: „Ha valaki matematikai eredményt ér el, ami 50 év legjobbja, akkor biztos, hogy valami jót csinál.”
**PSPACE: Az utolsó határ**
Williams új szimulációja pozitív eredményt hozott a tárhely számítási erejéről: a viszonylag kevés tárhelyet használó algoritmusok képesek megoldani azokat a feladatokat is, amelyek több időt igényelnek. Majd néhány soros matematikai fordulattal negatív következtetést is levont az idő számítási erejéről: néhány probléma nem oldható meg kevesebb idővel, mint amennyi tárhelyre szükség van. Ez a második, szűkebb eredmény megerősítette a kutatók várakozásait. A furcsa rész az, hogy Williams hogyan jutott el ide: először egy olyan eredményt bizonyított, amely minden algoritmusra érvényes, függetlenül attól, milyen problémát oldanak meg.
„Még mindig nehezemre esik elhinni” – mondta Williams. „Egyszerűen túl szép, hogy igaz legyen.” Minőségi szempontból Williams második eredménye akár a régóta keresett megoldásnak is tűnhet a P vs. PSPACE problémára. A különbség a méretben rejlik: míg a P és PSPACE nagyon széles komplexitási osztályok, addig Williams eredménye finomabb szinten működik. Kvantitatív szakadékot állapított meg a tárhely és az idő ereje között, és ahhoz, hogy a PSPACE valóban nagyobb legyen a P-nél, a kutatóknak ezt a szakadékot sokkal szélesebbre kell tárniuk.
Ez egy félelmetes kihívás, mintha egy járdarepedést feszítővasal tágítanánk, amíg el nem éri a Grand Canyon méretét. De talán lehetséges, ha Williams szimulációs eljárását többször ismételjük, minden lépésben egy keveset spórolva a tárhelyen. Ez olyan, mintha a feszítővasat folyamatosan meghosszabbítanánk – ha elég nagy, bármit szét lehet törni. A jelenlegi algoritmus verziójában ez az ismétlődő fejlesztés nem működik, de a kutatók nem tudják, hogy ez alapvető korlát-e.
„Lehet, hogy ez egy végső akadály, vagy egy 50 éves gát” – mondta Valiant. „De az is lehet, hogy valaki már a jövő héten megoldja.” Ha a probléma a jövő héten megoldódik, Williams biztosan dühös lesz magára – a cikk megírása előtt hónapokig próbálta kiterjeszteni az eredményét, sikertelenül. De még ha ez a kiterjesztés lehetetlen is, Williams biztos benne, hogy a további „térkutatás” érdekes eredményekhez vezethet – talán egy teljesen más probléma megoldásához.
„Sosem tudom pontosan bebizonyítani azt, amit szeretnék” – mondta. „De gyakran az, amit sikerül bizonyítanom, sokkal jobb, mint amit eredetileg akartam.”
*Szerkesztői megjegyzés: Scott Aaronson a Quanta Magazine tanácsadó testületének tagja.*
*Eredeti cikk a Quanta Magazinetől, a Simons Foundation szerkesztésében független tudományos lapjától.*
Ez a cikk a Neural News AI (V1) verziójával készült.
Forrás: https://www.wired.com/story/for-algorithms-a-little-memory-outweighs-a-lot-of-time/.
A képet Trnava University készítette, mely az Unsplash-on található.
