https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html Computational Complexity Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch Wednesday, February 26, 2025 You Need Much Less Memory than Time Just as I was complaining that we haven't seen many surprising breakthroughs in complexity recently, we get an earthquake of a result to start the year, showing that all algorithms can be simulated using considerable less memory than the time of the original algorithm. You can reuse space (memory) but you can't reuse time, and this new result from Ryan Williams in an upcoming STOC paper provides the first stark difference. DTIME(\(t(n)\)) \(\subseteq\) DSPACE(\(\sqrt{t(n)\log t(n)}\)) This is a vast improvement on the previous best known simulation, the classic 1977 Hopcroft-Paul-Valiant paper showing DTIME(\(t(n)\)) \(\subseteq\) DSPACE(\(t(n)/\log t(n)\)) only slightly lower than the trivial \(t(n)\) bound. Williams gets a huge near quadratic improvement that will go down as a true classic complexity theorem. Note that the space simulation does not maintain the time bound. Williams' proof relies on a space-efficient tree evaluation algorithm by James Cook and Ian Mertz from last year's STOC conference. Cook and Mertz's algorithm builds on earlier work on catalytic computing, highlighted in a recent Quanta article. Let me give an highly overly simplified view of the combined proof. A \(t(n)\) time Turing machine uses at most that much space on its tapes. Split the tapes into \(\sqrt{t(n)}\) segments of size \(\sqrt {t(n)}\). Using the fact that it takes \(\sqrt{t(n)}\) time to cross an entire segment, Williams with some clever tricks models acceptance of the Turing machines as a circuit of bounded degree and depth \(\ sqrt{t(n)}\), where the wires carry the contents of the size \(\sqrt {t(n)}\) segments at various times in the computation. Williams then applies the tree evaluation algorithm of Cook and Mertz. Cook and Mertz use finite fields to encode these segments as a combination of registers of size \(\log t(n)\) and show how to compute the value of each node of the tree using only \(\sqrt{t(n)}\) space for the local computation plus needing to only remember a constant number of registers while reusing the rest of the space when recursively computing the tree. It's pretty magical how they manage to make it all work. It's worth going through the proof yourself. I recommend Sections 3.1 and Footnote 6 in Williams' paper (a slightly weaker space bound but much simpler) and Sections 2-4 of the Cook-Mertz paper. Oded Goldreich has an alternative exposition of the Cook-Mertz algorithm and proof. Williams' theorem works for multitape Turing machines and oblivious random-access machines, where the queries to the memory are fixed in advance. He shows how to use this result to compute the output a circuit of size \(s\) using nearly \(\sqrt{s}\) space. Fully general random access machines remains open, as does nondeterministic and other models of computation (random, quantum, etc). In 1986 my advisor Mike Sipser gave the first hardness vs randomness result, showing roughly that if there were problems that took time \ (2^n\) but could not be solved in space \(2^{.99n}\) on multi-tape Turing machines then RP = P. Williams' theorem kills this assumption though we've developed weaker assumptions since. Moving forward, can we push Williams' result to get a simulation in space \(n^\epsilon\) for \(\epsilon<1/2\). A simulation for all \(\ epsilon>0\) would separate P from PSPACE. Even a slight improvement would have applications for alternating time. Maybe try to use the Cook-Mertz techniques directly in the Turing machine simulation instead of going through computation trees. Read sections 4 and 5 of Williams' paper for some further consequences and challenges for further improvements. Posted by Lance Fortnow at 8:47 AM # # Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest 15 comments: 1. [blank] EG10:31 AM, February 26, 2025 Sorry but is there a link to Williams' paper in this post? Am I missing something? ReplyDelete Replies 1. [fortnow] Lance Fortnow10:38 AM, February 26, 2025 The links to the papers are at the top of the post but I'll put them here: Williams and Cook-Mertz. Delete Replies Reply 2. [blank] Anonymous10:56 AM, February 26, 2025 Works now. Many thanks Delete Replies Reply Reply 2. [blank] Anonymous4:04 PM, February 27, 2025 Non-expert here. Is "random access machines remains open" related to the Turing machine argument "using the fact that it takes time to cross an entire segment"? Could we say this result is as much about the time-inefficiency of Turning machines as it is about the existence of space-efficient algorithms? ReplyDelete Replies 1. [blank] Anonymous9:42 AM, June 07, 2025 I was wondering the same. It seems the discovery applies within Turing Machines because they attribute linear time cost to head move distance. Drawing parallels to the role of cache locality for effective use of time in real-world computers seems intuitive, but vague. Delete Replies Reply Reply 3. [blank] Anonymous11:16 PM, February 27, 2025 I first read the post title as "You Need Much Less Money than Time", which would have been a great advice. ReplyDelete Replies Reply 4. [blank] EG7:42 AM, March 03, 2025 I wonder what Mihai Patrascu would have said about this development ... ReplyDelete Replies Reply 5. [blank] Anonymous2:14 PM, March 04, 2025 plenty of space and not enough time ReplyDelete Replies Reply 6. [blank] Anonymous5:47 PM, March 10, 2025 The New Scientist covered this breakthrough in an article (only available to subscribers) that contains some quotes from Lance: https://www.newscientist.com/article/ 2469663-shock-discovery-tears-up-the-rules-of-time-and-space-inside-a-computer / ReplyDelete Replies Reply 7. [fortnow] Lance Fortnow7:58 AM, March 17, 2025 Minor breakthroughs, yes and within a couple of years. Major breakthroughs--don't count on it. ReplyDelete Replies Reply 8. [blank] Anonymous5:22 PM, March 17, 2025 Assume that you know that you will first know breakthrough x at time y, which is in the future. This means you also know x now, in the present. This contradicts the assumption. Therefore, you cannot predict what you will learn in the future. David Deutsch puts it this way: "A simple example, if there were a method of predicting today some scientific truth that is only going to be discovered next year, then by using that method, we would have gained that knowledge today, and that's a contradiction." See https://medium.com/dorothyknows/ david-deutsch-the-unknowable-how-to-prepare-for-it-e1b2c7d78744 ReplyDelete Replies Reply 9. [blank] Anonymous7:01 PM, March 23, 2025 Wouldn't P in Logspace be a surprise? ReplyDelete Replies Reply 10. [blank] Anonymous7:55 PM, June 07, 2025 We can't create more time, but we can create more memory. So, why would one not use more memory if it saves some time? I somewhat understand the theoretical aspects... but where would this new research be useful in a world where programs are expected to compute results in millisecond SLAs? ReplyDelete Replies 1. [blank] Anonymous4:13 AM, June 08, 2025 Unused cpu time is not impacting total computation time. Task taking 2 milliS, is just making more compute (with less memory?) running at 100% than running at 50%. Delete Replies Reply Reply 11. [blank] Defdefred4:09 AM, June 08, 2025 Funny thing is that memory is regulary the constraint in virtualized infra, while CPU have lots of idle time... So everything is badly coded? ReplyDelete Replies Reply Add comment Load more... Newer Post Older Post Home Subscribe to: Post Comments (Atom) Books [9780691175] Commissions earned from Amazon Links Mastodon Feed Blog Links * Bill's Home Page * Lance's Home Page * Posts Feed * Comments Feed * Favorite Theorems * Foundations of Complexity Lessons * Graduate Student Guide * ChatPNP * Ask Questions to the Blog * CACM P v NP Survey (2009) * CACM Fifty Years of P vs. NP (2022) * CACM Conference Viewpoint * Podcasts * Videos Popular Posts * FOCS Accepts and a Movie * Intelligent questions about the alleged P NE NP proof * You Need Much Less Memory than Time * The 17x17 challenge. Worth $289.00. This is not a joke. * What was the recent Nobel Prize in Physics really about?(Guest Post) * The Problems of LaTeX * Why did 1+1=2 take Russell and Whitehead 300 pages? * NRC Rankings * Is this problem too hard for a HS Math Competition * Random Thought on the New Pope (the actual New Pope, not the TV series). He was a math major! Complexity Links * Complexity Conference * SIGACT * Theory Announcements * Theory Stack Exchange * Complexity Zoo * Complexity on arXiv * Electronic Colloquium on Computational Complexity Blog Archive * V 2025 (43) + > June (2) + > May (8) + > April (8) + > March (9) + V February (6) o You Need Much Less Memory than Time o Why my department hopes I do not die this spring o Tomorrow and Yesterday o Big Breakthrough in the exciting world of sum-free... o Research Then and Now o Does Lance dislike Ramsey Theory Because he's colo... + > January (10) * > 2024 (102) + > December (7) + > November (7) + > October (9) + > September (9) + > August (7) + > July (8) + > June (11) + > May (9) + > April (9) + > March (8) + > February (8) + > January (10) * > 2023 (92) + > December (6) + > November (8) + > October (8) + > September (7) + > August (8) + > July (9) + > June (6) + > May (9) + > April (7) + > March (8) + > February (8) + > January (8) * > 2022 (77) + > December (7) + > November (7) + > October (9) + > September (6) + > August (7) + > July (6) + > June (5) + > May (6) + > April (5) + > March (6) + > February (7) + > January (6) * > 2021 (89) + > December (6) + > November (7) + > October (8) + > September (8) + > August (9) + > July (7) + > June (7) + > May (8) + > April (8) + > March (7) + > February (6) + > January (8) * > 2020 (76) + > December (8) + > November (7) + > October (7) + > September (7) + > August (6) + > July (6) + > June (6) + > May (7) + > April (7) + > March (9) + > February (1) + > January (5) * > 2019 (84) + > December (4) + > November (3) + > October (8) + > September (7) + > August (2) + > July (8) + > June (9) + > May (9) + > April (9) + > March (8) + > February (8) + > January (9) * > 2018 (100) + > December (7) + > November (8) + > October (10) + > September (8) + > August (9) + > July (8) + > June (8) + > May (9) + > April (9) + > March (8) + > February (8) + > January (8) * > 2017 (102) + > December (7) + > November (8) + > October (9) + > September (8) + > August (9) + > July (9) + > June (9) + > May (9) + > April (9) + > March (8) + > February (8) + > January (9) * > 2016 (102) + > December (9) + > November (8) + > October (9) + > September (7) + > August (8) + > July (7) + > June (10) + > May (9) + > April (10) + > March (8) + > February (9) + > January (8) * > 2015 (103) + > December (7) + > November (9) + > October (9) + > September (8) + > August (9) + > July (9) + > June (10) + > May (8) + > April (9) + > March (9) + > February (8) + > January (8) * > 2014 (111) + > December (8) + > November (8) + > October (10) + > September (11) + > August (9) + > July (9) + > June (11) + > May (10) + > April (10) + > March (8) + > February (8) + > January (9) * > 2013 (108) + > December (9) + > November (8) + > October (8) + > September (11) + > August (9) + > July (9) + > June (8) + > May (9) + > April (10) + > March (9) + > February (9) + > January (9) * > 2012 (132) + > December (7) + > November (9) + > October (12) + > September (10) + > August (10) + > July (9) + > June (10) + > May (12) + > April (12) + > March (15) + > February (14) + > January (12) * > 2011 (134) + > December (10) + > November (10) + > October (12) + > September (13) + > August (10) + > July (10) + > June (14) + > May (11) + > April (12) + > March (12) + > February (11) + > January (9) * > 2010 (191) + > December (8) + > November (12) + > October (15) + > September (14) + > August (18) + > July (15) + > June (17) + > May (20) + > April (22) + > March (20) + > February (15) + > January (15) * > 2009 (249) + > December (16) + > November (19) + > October (23) + > September (21) + > August (21) + > July (23) + > June (23) + > May (22) + > April (21) + > March (22) + > February (20) + > January (18) * > 2008 (253) + > December (19) + > November (18) + > October (27) + > September (21) + > August (19) + > July (22) + > June (23) + > May (23) + > April (22) + > March (20) + > February (21) + > January (18) * > 2007 (159) + > December (10) + > November (15) + > October (18) + > September (10) + > August (13) + > July (11) + > June (8) + > May (8) + > April (7) + > March (16) + > February (20) + > January (23) * > 2006 (238) + > December (18) + > November (22) + > October (22) + > September (19) + > August (24) + > July (18) + > June (18) + > May (18) + > April (18) + > March (21) + > February (20) + > January (20) * > 2005 (237) + > December (18) + > November (20) + > October (24) + > September (19) + > August (22) + > July (17) + > June (19) + > May (21) + > April (19) + > March (17) + > February (17) + > January (24) * > 2004 (200) + > December (18) + > November (16) + > October (19) + > September (15) + > August (16) + > July (15) + > June (18) + > May (13) + > April (13) + > March (17) + > February (16) + > January (24) * > 2003 (149) + > December (13) + > November (12) + > October (15) + > September (11) + > August (7) + > July (11) + > June (13) + > May (10) + > April (15) + > March (15) + > February (11) + > January (16) * > 2002 (76) + > December (20) + > November (17) + > October (15) + > September (18) + > August (6) Blog Roll * GovAffairs Department of Energy FY 2026 Request: ASCR Flat Funded While Office of Science Receives Significant Cut 2 days ago * Combinatorics and more Erdos Lectures 2025: Mehtaab S. Sawhney, June 5,9 & 11 3 days ago * What's new Decomposing a factorial into large factors (second version) 4 days ago * Daniel Lemire's blog Fast character classification with z3 1 week ago * 11011110 Linkage 1 week ago * Shtetl-Optimized "If Anyone Builds It, Everyone Dies" 1 week ago * Mathematical Enchantments Math and the Museum 2 weeks ago * Thoughts Minimalistic combat, and Sifu 3 weeks ago * Process Algebra Diary PhD Position in Probabilistic Session Types at the IT University of Copenhagen 4 weeks ago * Theory Dish Choosing the best ring ... for MPC! 1 month ago * Windows On Theory Call for papers Information-Theoretic Crpytography 2 months ago * Turing's Invisible Hand 2025 Godel Prize: Call for Nominations (Due April 11) 3 months ago * Healthy Algorithms AI for Interview Prep 4 months ago * Godel's Lost Letter and P=NP 5 months ago * Bits and Pieces Bill Ackman's Analysis of Harvard 8 months ago * Theory Matters FOCS 2024 Test of Time Awards Nominations 11 months ago * in theory FOCS Test of Time Awards 1 year ago * The Big Data Theory How I Spent Last Summer FAQ 5 years ago * Opinions of Doron Zeilberger Show 10 Show All Creative Commons License Computational Complexity Weblog by Lance Fortnow and William Gasarch is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Additional permissions can be requested. Powered by Blogger.