That classic result was a way to transform any algorithm with a given time budget into a new algorithm with a slightly smaller space budget. Williams saw that a simulation based on squishy pebbles would make the new algorithm\u2019s space usage much smaller\u2014roughly equal to the square root of the original algorithm\u2019s time budget. That new space-efficient algorithm would also be much slower, so the simulation was not likely to have practical applications. But from a theoretical point of view, it was nothing short of revolutionary.<\/p>\n
For 50 years, researchers had assumed it was impossible to improve Hopcroft, Paul and Valiant\u2019s universal simulation. Williams\u2019 idea\u2014if it worked\u2014wouldn\u2019t just beat their record\u2014it would demolish it.<\/p>\n
\u201cI thought about it, and I was like, \u2018Well, that just simply can\u2019t be true,\u2019\u201d Williams said. He set it aside and didn\u2019t come back to it until that fateful day in July, when he tried to find the flaw in the argument and failed. After he realized that there was no flaw, he spent months writing and rewriting the proof to make it as clear as possible.<\/p>\n
At the end of February, Williams finally put the finished paper online<\/a>. Cook and Mertz were as surprised as everyone else. \u201cI had to go take a long walk before doing anything else,\u201d Mertz said.<\/p>\n Valiant got a sneak preview of Williams\u2019 improvement on his decades-old result during his morning commute. For years, he\u2019s taught at Harvard University, just down the road from Williams\u2019 office at MIT. They\u2019d met before, but they didn\u2019t know they lived in the same neighborhood until they bumped into each other on the bus on a snowy February day, a few weeks before the result was public. Williams described his proof to the startled Valiant and promised to send along his paper.<\/p>\n \u201cI was very, very impressed,\u201d Valiant said. \u201cIf you get any mathematical result which is the best thing in 50 years, you must be doing something right.\u201d<\/p>\n PSPACE: The Final Frontier<\/p>\n With his new simulation, Williams had proved a positive result about the computational power of space: Algorithms that use relatively little space can solve all problems that require a somewhat larger amount of time. Then, using just a few lines of math, he flipped that around and proved a negative result about the computational power of time: At least a few problems can\u2019t be solved unless you use more time than space. That second, narrower result is in line with what researchers expected. The weird part is how Williams got there, by first proving a result that applies to all algorithms, no matter what problems they solve.<\/p>\n \u201cI still have a hard time believing it,\u201d Williams said. \u201cIt just seems too good to be true.\u201d<\/p>\n Williams used Cook and Mertz\u2019s technique to establish a stronger link between space and time\u2014the first progress on that problem in 50 years.Photograph: Katherine Taylor for Quanta Magazine<\/p>\n Phrased in qualitative terms, Williams\u2019 second result may sound like the long-sought solution to the P versus PSPACE problem. The difference is a matter of scale. P and PSPACE are very broad complexity classes, while Williams\u2019 results work at a finer level. He established a quantitative gap between the power of space and the power of time, and to prove that PSPACE is larger than P, researchers will have to make that gap much, much wider.<\/p>\n That\u2019s a daunting challenge, akin to prying apart a sidewalk crack with a crowbar until it\u2019s as wide as the Grand Canyon. But it might be possible to get there by using a modified version of Williams\u2019 simulation procedure that repeats the key step many times, saving a bit of space each time. It\u2019s like a way to repeatedly ratchet up the length of your crowbar\u2014make it big enough, and you can pry open anything. That repeated improvement doesn\u2019t work with the current version of the algorithm, but researchers don\u2019t know whether that\u2019s a fundamental limitation.<\/p>\n \u201cIt could be an ultimate bottleneck, or it could be a 50-year bottleneck,\u201d Valiant said. \u201cOr it could be something which maybe someone can solve next week.\u201d<\/p>\n If the problem is solved next week, Williams will be kicking himself. Before he wrote the paper, he spent months trying and failing to extend his result. But even if such an extension is not possible, Williams is confident that more space exploration is bound to lead somewhere interesting\u2014perhaps progress on an entirely different problem.<\/p>\n \u201cI can never prove precisely the things that I want to prove,\u201d he said. \u201cBut often, the thing I prove is way better than what I wanted.\u201d<\/p>\n Editor\u2019s note: Scott Aaronson is a member of\u00a0Quanta Magazine\u2019s\u00a0advisory board<\/a>.<\/p>\n Original story<\/a> reprinted with permission from Quanta Magazine<\/a>, an editorially independent publication of the Simons Foundation<\/a> whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.<\/p>\n","protected":false},"excerpt":{"rendered":"That classic result was a way to transform any algorithm with a given time budget into a new…\n","protected":false},"author":2,"featured_media":7505,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[21],"tags":[3974,64,63,8216,257,9451,128,105],"class_list":{"0":"post-7504","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-computing","8":"tag-algorithms","9":"tag-au","10":"tag-australia","11":"tag-computer-science","12":"tag-computing","13":"tag-quanta-magazine","14":"tag-science","15":"tag-technology"},"_links":{"self":[{"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/posts\/7504","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/comments?post=7504"}],"version-history":[{"count":0,"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/posts\/7504\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/media\/7505"}],"wp:attachment":[{"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/media?parent=7504"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/categories?post=7504"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.newsbeep.com\/au\/wp-json\/wp\/v2\/tags?post=7504"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}