Tid og hukommelsesrum er de to vigtigste begrænsninger for, hvad vi kan beregne, og at forstå deres forhold er en vigtig del af beregningskompleksitetsforskning
Hvordan relaterer tid og rum til beregning? Vi har et nyt svar
En forbløffende opdagelse af forholdet mellem mængden af hukommelse, som en beregning kræver, og hvor lang tid det tager har vugget computerforskere – selvom det ikke er klart, om der er nogen praktiske applikationer.
”Det ryster slags min verdenssyn,” siger Ryan Williams ved Massachusetts Institute of Technology, der fandt opdagelsen. ”Jeg er stadig bare chokeret over, at det endda eksisterer.”
Tid og hukommelsesrum er de to vigtigste begrænsninger for, hvad vi kan beregne. Nogle problemer kræver masser af hukommelse, nogle masser af tid, og mange kræver meget af begge dele. At studere disse begrænsninger er domænet for beregningskompleksitetsforskere, der omtaler tid som antallet af trin, en computer tager for at udføre en bestemt opgave, og plads som antallet af hukommelseslots, som opgaven kræver.
Intuitivt er disse værdier forbundet, for hvis en opgave kræver X -trin, i værste fald scenarie, hvor computeren har brug for at få adgang til hukommelsen for hvert trin, kræver den X -hukommelsespladser.
Men forskere har været i stand til at sænke baren for den mængde hukommelse, der kræves i dette værste tilfælde. I 1970’erne blev det opdaget, at faktisk enhver beregning, der tager X -trin, kunne udføres med X/Log X hukommelse. Så et program, der tog 100 tidstrin, kunne for eksempel altid køre inden for 50 hukommelsespladser, da log 100 er lig med 2.
”Det er det bedste, vi har kendt indtil i sidste uge,” siger Lance Fortnow ved Illinois Institute of Technology. Men så frigav Williams et overraskende papir, der viste, at dette kan reduceres dramatisk-til kvadratroten af X Log X. I stedet for 100 eller 50 hukommelsespladser, kunne et 100-trins problem faktisk reduceres til 15 slots.
”Det var lidt af en shocker, da Ryan sendte dette papir rundt i sidste uge, og vi var alle som,” wow ”,” siger Fortnow.
Williams blev selv overrasket. ”Det tog mig måneder at overbevise mig selv om, at det ikke bare var åbenlyst falsk,” siger han. ”Det er stadig meget vanskeligt for mig at vikle hovedet rundt om det. Jeg kan gennemgå alle trin, beviset og verificere hvert trin er korrekt, og at det er sandt. Men i slutningen undrer jeg mig stadig over. ”
Fundet lyder usandsynligt, fordi det betyder, at computere ser ud til kun at have brug for plads til at holde en lille del af et problem i hukommelsen-lidt som mennesker, der er i stand til at løse et komplekst, multi-trins matematikproblem uden behov for at skrive alt ned, idet de kun er afhængige af vores begrænsede korttidshukommelse.
Williams ’tilgang hænger sammen med det, der er kendt som træevalueringsproblemet. Dette involverer en række sammenkoblede beregninger i en forgrenet træformet struktur, hvor beregning af det endelige resultat ved “rod” af træet først involverer beregning af “blade”, derefter “grene” og så videre. De seneste fremskridt med at løse træevalueringsproblemet har vist, at det er muligt at gøre det med en algoritme, der er i stand til at genbruge computerhukommelse, der allerede er fuld-i sig selv en helt uventet opdagelse.
For at bringe dette til at bære spørgsmålet om tid og rum oprettede Williams en model, der kan repræsentere ethvert beregningsproblem, og derefter anvendte den nye træevalueringsalgoritme, hvilket viste, at den drastisk kunne reducere den krævede mængde hukommelse. Det involverer matematiske tricks og “magiske aflysninger”, der i sidste ende giver gyldige svar, siger han.
“Det føles ud over spændende,” siger Ian Mertz ved Charles University i Tjekkiet, en af forskerne, der udviklede den nye algoritme. “Absolut et counterintuitivt resultat, selvom jeg ville sige, at vores træevalueringsalgoritmer allerede var temmelig modstridende.”
Men mens omfanget af opdagelsen har chokeret computerforskere, ændrer det ikke nødvendigvis den måde, vi bruger computere på. Problemet er, at konstateringen viser, at selvom du kan krympe mængden af hukommelse, der kræves for at udføre en beregning, vil det ikke reducere den tid, det tager. Computerhukommelse er temmelig billig og let tilgængelig, så det er en prioritet at reducere det beløb, vi har brug for.
En opdagelse, der muliggjorde det modsatte, ville betyde, at vi kunne tilføje mere hukommelse til computere og hurtige beregning som et resultat – noget, der ville være meget nyttigt, da fremskridt i processorhastighed er begyndt at bremse – men om dette ville være muligt er uklart. “Nu hvor vi ved, at tidseffektive algoritmer kan gøres pladseffektive, kan vi kigge efter afvejninger, der er temmelig gode til både tid og plads på samme tid, og det er nyttigt i en reel forstand,” siger Mertz.
Fortnow siger, at han ikke ser nogen øjeblikkelige praktiske konsekvenser for arbejdet, men påpeger, at det giver håb om, at flere overraskelser i beregningskompleksiteten stadig kunne komme, og at de måske ryster, hvordan vi løser hårde problemer. ”Du er chokeret en gang, du kan blive chokeret igen,” siger han.