Simulating Time in Square-Root Space | Hacker News Reader

Simulating Time in Square-Root Space

eccc.weizmann.ac.il

109 pointsEvgeniyZh15 comments

This 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

1. https://www.quantamagazine.org/catalytic-computing-taps-the-...

Wait, it's the same Cook who proved that SAT is NP-complete somewhere during the cold war? I had no idea this guy was still around doing research.

It's not the same Cook, but rather his son.

That's almost equally awesome

And the original paper: https://eccc.weizmann.ac.il/report/2023/174/

This 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.

Blog post from Scott Aaronson https://scottaaronson.blog/?p=8680

(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

To 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.

It 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)

Yes, 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.

I've always found it odd that people are fixating on showing P != NP when they can't even show that P != PSPACE.

How 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.

It takes constant space.

Yes.

In general, big-O notation only really makes sense, if you generalise your problems to take some potentially arbitrarily large input.

Often that generalisation is only implied, thus confusing the unwary reader.

Reply on news.ycombinator.com