4 ms·
Simulating Time in Square-Root Space
- croissants 2y ago(To appear at STOC 2025 [1], one of the top CS theory conferences, so it's passed peer review.) [1] https://acm-stoc.org/stoc2025/accepted-papers.html https://acm-stoc.org/stoc2025/accepted-papers.html
- eru 2y agoTo give a bit of context (context that wasn't obvious just from the abstract, at least to me): this paper makes progress on, amongst other things, P!=NP.
- LPisGood 2y agoIt makes more progress on P != PSPACE, which is a ridiculously big class containing the entire polynomial hierarchy (PH is essentially the union over all n of NP recursively relativized to itself n many times)
- eru 2y agoYes, I know. But I assumed that people would be more familiar with P vs NP. Specifically, we know that P <= NP <= PSPACE. And any progress on P < NP would automatically involve some progress on P < PSPACE. And while a proof of P < PSPACE by itself wouldn't strictly say anything about P vs NP directly, it would probably at least give some inspiration and hints.
- IsTom 2y agoI've always found it odd that people are fixating on showing P != NP when they can't even show that P != PSPACE.
- nsoonhui 2y agoBlog post from Scott Aaronson https://scottaaronson.blog/?p=8680 https://scottaaronson.blog/?p=8680
- robinhouston 2y agoThis cool result relies on an amazing algorithm that was discovered last year: the Cook-Mertz tree evaluation procedure. See [0] for an exposition, or [1] for a recent popular article about it. 0. https://www.wisdom.weizmann.ac.il/~oded/p_TreeEval.html https://www.wisdom.weizmann.ac.il/~oded/p_TreeEval.html 1. https://www.quantamagazine.org/catalytic-computing-taps-the-full-power-of-a-full-hard-drive-20250218/ https://www.quantamagazine.org/catalytic-computing-taps-the-...
- CGamesPlay 2y agoHow much space does it take to factor a 2048-bit integer? Just plugging the numbers into the big-O notation, it's just some constant times a modest 8.466×10^296 TB.
- LPisGood 2y agoThis reminds me of the joke from Ergodic theory that a lazy physicist can check for phenomena by only looking square numbers. To elaborate, Poincare recurrence says that certain nice dynamical systems will always return to near their original state after finite time, and by Sarkozy’s theorem any set which contains infinitely many pairs of terms that differ by a square is in some sense big enough to observe that recurrence.