Ez a klasszikus eredmény lehetővé tette, hogy bármely adott időkerettel rendelkező algoritmust átalakítsunk egy olyan új algoritmussá, amely kicsit kisebb 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. Az új, tárhelyhatékony algoritmus azonban sokkal lassabb lett volna, így a szimulációnak valószínűleg nem lennak gyakorlati alkalmazásai. Elméleti szempontból azonban forradalmi jelentőségű volt.
50 éven át a kutatók azt hitték, hogy lehetetlen javítani Hopcroft, Paul és Valiant univerzális szimulációs módszerén. Williams ötlete – ha működik – nemcsak megdöntötte volna a rekordot, hanem teljesen felülmúlta volna azt. „Gondolkodtam rajta, és azt mondtam: ›Ez egyszerűen nem lehet igaz‹” – emlékezett Williams. Félretette az ötletet, és csak akkor tért vissza hozzá, amikor egy júliusi napon megpróbálta megtalálni a hibát az elméletben – és nem talált. Miután rájött, hogy nincs hiba, hónapokig dolgozott a bizonyítás tökéletesíté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 előzetesen ismerhette Williams javítását a saját évtizedes eredményére, amikor reggel a buszon találkoztak. Bár korábban is találkoztak, csak most tudták meg, hogy egy környéken laknak. Williams elmagyarázta a bizonyítást a meglepett Valiantnak, aki lenyűgözve reagált: „Ha valaki olyan matematikai eredményt ér el, ami 50 év óta a legjobb, akkor biztos, hogy valamit jól csinál.”
A 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 problémákat, 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 elvárá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.”
Williams Cook és Mertz technikáját felhasználva erősebb kapcsolatot hozott létre a tárhely és az idő között – ez volt az első jelentős előrelépés ezen a területen 50 év után. Minőségi szempontból Williams második eredménye akár a régóta keresett megoldásnak is tűnhet a P és a PSPACE közötti problémára. A különbség a méretben rejlik. A P és a PSPACE nagyon széles komplexitási osztályok, míg Williams eredményei finomabb szinten működnek. Kvantitatív különbséget állapított meg a tárhely és az idő ereje között, és ahhoz, hogy a PSPACE nagyobb legyen a P-nél, a kutatóknak ezt a szakadékot sokkal, sokkal szélesebbre kell tenniük.
Ez egy félelmetes kihívás, mintha egy járdarepedést feszítővassal tágítanánk, amíg el nem éri a Grand Canyon méretét. De talán lehetséges elérni, ha Williams szimulációs eljárását többször ismételjük, minden lépésben egy kicsit megtakarítva a tárhelyből. Ez olyan, mintha a feszítővas hosszát folyamatosan növelnénk – ha elég nagy, bármit fel lehet vele 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 akadály” – mondta Valiant. „Vagy lehet, hogy valaki már a jövő héten megoldja.”
Ha a probléma a jövő héten megoldódik, Williams biztosan bosszankodni fog. 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 nem is lehetséges, 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 bizonyítani azt, amit bizonyítani akarok” – mondta. „De gyakran az, amit sikerül bizonyítanom, sokkal jobb, mint amit eredetileg szerettem volna.”
Szerkesztői megjegyzés: Scott Aaronson a Quanta Magazine tanácsadó testületének tagja.
Az eredeti cikk a Quanta Magazine engedélyével került közreadásra. A Quanta Magazine a Simons Foundation független szerkesztésű kiadványa, amely a matematika, a fizika és az élettudományok területén kutatási fejleményeket és trendeket mutat be, hogy növelje a tudományos ismeretek terjedését.
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ó.
