Taj klasični rezultat bio je način da se bilo koji algoritam pretvori s određenim vremenskim proračunom u novi algoritam s nešto manjim svemirskim proračunom. Williams je vidio da će simulacija utemeljena na škljocnom šljuncima učiniti novi algoritam mnogo manjim – otprilike jednakom kvadratnom korijenu izvornog proračuna za algoritam. Taj bi novi algoritam učinkovitih prostora također bio mnogo sporiji, tako da simulacija vjerojatno neće imati praktične primjene. Ali s teorijskog stajališta, to nije bilo ništa drugo revolucionarno.
50 godina su istraživači pretpostavili da je nemoguće poboljšati Univerzalnu simulaciju Hopcrofta, Paula i Valiant -a. Williamsova ideja – ako je uspjela – ne bi samo pobijedila njihov rekord – srušila bi je.
“Razmišljao sam o tome i rekao sam:” Pa, to jednostavno ne može biti istina “, rekao je Williams. Odložio ga je i nije mu se vratio do tog sudbonosnog dana u srpnju, kada je pokušao pronaći manu u svađi i nije uspio. Nakon što je shvatio da nema nedostatka, proveo je mjesecima pišući i prepisao dokaz kako bi bio što jasniji.
Krajem veljače, Williams napokon Stavite gotov papir na mreži. Cook i Mertz bili su iznenađeni kao i svi drugi. “Morao sam ići dugo prije nego što učinim bilo što drugo”, rekao je Mertz.
Valiant je dobio pregledni pregled Williamsovog poboljšanja na njegovom desetljećima starim rezultatima tijekom jutarnjeg putovanja. Godinama je predavao na Sveučilištu Harvard, tik uz put od Williamsovog ureda na MIT -u. Prije su se sreli, ali nisu znali da žive u istom susjedstvu dok se na autobus naletjeli na autobus, nekoliko tjedana prije nego što je rezultat bio javan. Williams je opisao svoj dokaz zaprepaštenom odvažnom i obećao da će poslati svoj rad.
“Bio sam jako, vrlo impresioniran”, rekao je Valiant. “Ako dobijete bilo kakav matematički rezultat, što je najbolja stvar u 50 godina, morate nešto raditi kako treba.”
PSPACE: Posljednja granica
Svojom novom simulacijom Williams je dokazao pozitivan rezultat u vezi s računalnom snagom prostora: algoritmi koji koriste relativno malo prostora mogu riješiti sve probleme koji zahtijevaju nešto veće vrijeme. Zatim je koristeći samo nekoliko redaka matematike, to je prebacio i dokazao negativan rezultat o računalnoj snazi vremena: barem se nekoliko problema ne može riješiti ako ne koristite više vremena od prostora. Taj drugi, uži rezultat je u skladu s onim što su istraživači očekivali. Čudan dio je kako je Williams tamo stigao, prvo dokazujući rezultat koji se odnosi na sve algoritme, bez obzira na to koje probleme rješavaju.
“Još uvijek mi je teško vjerovati”, rekao je Williams. “Čini se da je previše dobro da bi bilo istinito.”
Williams je koristio Cook i Mertzovu tehniku kako bi uspostavio jaču vezu između prostora i vremena – prvi napredak u tom problemu u 50 godina.Fotografija: Katherine Taylor za časopis Quanta
Frazirano u kvalitativnom smislu, Williamsov drugi rezultat može zvučati kao dugo traženo rješenje za P-PSPACE problem. Razlika je stvar razmjera. P i PSPACE su vrlo široke klase složenosti, dok Williamsovi rezultati djeluju na finijoj razini. Uspostavio je kvantitativni jaz između snage prostora i snage vremena i dokazati da je PSPACE veći od P, istraživači će taj jaz morati učiniti mnogo, mnogo širim.
To je zastrašujući izazov, sličan razdvajanju pločnika pukotina s kružnim trakom dok ne bude širok kao Grand Canyon. Ali možda bi bilo moguće doći tamo pomoću modificirane verzije Williamsovog simulacijskog postupka koja više puta ponavlja ključni korak, svaki put štedeći malo prostora. To je poput načina da se više puta pojačate duljinu vaše lopove – napravite ga dovoljno veliko, i možete otvoriti bilo što. To ponovljeno poboljšanje ne djeluje s trenutnom verzijom algoritma, ali istraživači ne znaju je li to temeljno ograničenje.
“To bi moglo biti krajnje usko grlo ili bi moglo biti 50-godišnje usko grlo”, rekao je Valiant. “Ili bi to moglo biti nešto što možda netko može riješiti sljedeći tjedan.”
Ako je problem riješen sljedeći tjedan, Williams će se udariti. Prije nego što je napisao novine, proveo je mjesecima pokušavajući i nije produžio rezultat. Ali čak i ako takvo proširenje nije moguće, Williams je uvjeren da će više svemirskog istraživanja voditi negdje zanimljivo – možda napredak u potpuno drugačijem problemu.
“Nikada ne mogu dokazati upravo ono što želim dokazati”, rekao je. “Ali često je stvar koju dokazujem mnogo bolja od onoga što sam želio.”
Napomena urednika: Scott Aaronson član je časopisa Quanta savjetodavni odbor.
Originalna priča ponovljena s dopuštenjem iz Magazin Quantaurednička neovisna publikacija Fondacija Simons Čija je misija poboljšati javno razumijevanje znanosti pokrivanjem razvoja istraživanja i trendova iz matematike i fizičkih i životnih znanosti.