Zašto dodavanje punog tvrdog diska može učiniti računalo moćnijim

To su prilično stroga ograničenja, tako da nije bilo očito da bi se dodatna memorija ikad mogla pokazati korisnom. No, na njihovo iznenađenje, Buhrman i Cleve pokazali su da, ako ugađate bitove na pravi način, zaista možete izvući dodatnu računalnu Oomph iz pune memorije.

“To je bio šok za sve”, rekao je Loff, koji je u to vrijeme bio diplomski student u Buhrmanovoj grupi, radeći na pitanju za sjećanje sa svojim kolegama Florian Speelman. Tim je ubrzo proširio rezultat na još veću klasu problema i objavio njihovi kombinirani rezultati u 2014. godini.

Nazvali su novi okvirni katalitičko računanje, posuđujući termin iz kemije. “Bez katalizatora, reakcija ne bi nastavila”, rekao je Raghunath Tewariteoretičar složenosti na Indijskom tehnološkom institutu, Kanpur. “Ali sam katalizator ostaje nepromijenjen.”

Nedaleko od stabla

Mali bend istraživača nastavio je dalje razvijati katalitičko računanje, ali nitko ga nije ni pokušao primijeniti na problem evaluacije stabala koji je u početku nadahnuo Kouckýjevu potragu. Za taj problem, preostalo otvoreno pitanje bilo je može li se mala količina memorije istovremeno koristiti za pohranu i računanje. No, tehnike katalitičkog računanja oslanjale su se na dodatnu, punu memoriju vrlo velike. Smanjite tu memoriju i tehnike više ne rade.

Ipak, jedan mladi istraživač nije se mogao zapitati postoji li način da se prilagodi te tehnike za ponovnu upotrebu pamćenja u algoritmu za procjenu stabla. Njegovo je ime bilo James CookA za njega je problem procjene stabala bio osobni: Stephen Cook, legendarni teoretičar složenosti koji ga je izmislio, njegov je otac. James je čak radio na tome u diplomskoj školi, iako se uglavnom fokusirao na Potpuno nepovezani subjekti. Kad je 2014. godine naišao na originalni katalitički računalni rad, James je trebao diplomirati i ostaviti akademsku zajednicu za softverski inženjering. Ali čak i dok se smjestio u svoj novi posao, nastavio je razmišljati o katalitičkom računanju.

“Morao sam to razumjeti i vidjeti što se može učiniti”, rekao je.

Godinama je James Cook u slobodno vrijeme zaletio katalitičkim pristupom problemu s procjenom drveća. Razgovarao je o svom napretku na simpoziju 2019. u čast očeva revolucionarni rad U teoriji složenosti. Nakon razgovora, prišao mu je diplomski student po imenu Ian Mertzkoji su se zaljubili u katalitičko računanje pet godina ranije nakon što je o tome saznao kao dojmljivog mladog undergrad -a.

“Bilo je to poput scenarija utiskivanja ptica za bebe”, rekao je Mertz.

Cook i Mertz udružili su snage, a njihovi se napori ubrzo isplatili. 2020. osmislili su algoritam To je riješilo problem s procjenom stabla s manje memorije od potrebnog minimalnog pretpostavljenih od strane starijeg Cook i McKenzie – iako je to bio jedva ispod tog praga. Ipak, to je bilo dovoljno za prikupljanje na okladi od 100 USD; Povoljno za kuhare, polovica je ostala u obitelji.

Ali još je bilo posla. Istraživači su počeli proučavati evaluaciju stabala jer se činilo kao da bi konačno mogao pružiti primjer problema u P koji nije u L – drugim riječima, relativno jednostavan problem koji se ne može riješiti pomoću vrlo malo memorije. Nova metoda Cook i Mertz koristila je manje memorije od bilo kojeg drugog algoritma za procjenu stabla, ali i dalje je koristila znatno više od bilo kojeg algoritma za problem u L. Procjena stabla je bila smanjena, ali ne i izvan.

Godine 2023. Cook i Mertz su izašli s Poboljšani algoritam To je koristilo mnogo manje memorije – uglavnom više od maksimalnog dopuštenog za probleme u L. Mnogi istraživači sada sumnjaju da je procjena stabala u L i da je dokaz samo pitanje vremena. Teoretičari složenosti možda će trebati drugačiji pristup problemu P u odnosu na L.

U međuvremenu, rezultati Cook i Mertz poticali su interes za katalitičko računanje, a novi radovi istražuju Priključci na slučajnost i učinci dopuštanja a nekoliko pogreške u resetiranju pune memorije u prvobitno stanje.

“Nismo završili s istraživanjem onoga što možemo učiniti s tim novim tehnikama”, rekao je McKenzie. “Možemo očekivati ​​još više iznenađenja.”

Originalna priča ponovljena s dopuštenjem iz Magazin Quanta,, urednič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.