Ryan Williams strikes again
- Because of a recent breakthrough by Cook and Mertz on Tree Evaluation, Ryan now shows that every problem solvable in t time on a multitape Turing machine is also solvable in close to √t space
- As a consequence, he shows that there are problems solvable in O(n) space that require nearly quadratic time on multitape Turing machines
- If this could be applied recursively to boost the polynomial degree, then P≠PSPACE
- On Facebook, someone summarized this result as “there exists an elephant that can’t fit through a mouse hole.” I pointed out that for decades, we only knew how to show there was a blue whale that didn’t fit through the mouse hole
- I’ll be off the Internet for much of today (hopefully only today?) because of jury duty! Good thing you’ll have Ryan’s amazing new paper to keep y’all busy…
Click to rate this post!
[Total: 0 Average: 0]
You have already voted for this article
(Visited 8 times, 1 visits today)