zlacker

>>makira+(OP)
I think it is very intuitive that more space beats the pants off of more time.

In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

>>LPisGo+Y9
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.

>>thatgu+pb
The article is about a new proof wherein P == PSPACE.

Something we all intuitively expected but someone finally figured out an obscure way to prove it.

--------

This is a really roundabout article that takes a meandering path to a total bombshell in the field of complexity theory. Sorry for spoiling but uhhh, you'd expect an article about P == PSPACE would get to the point faster....

>>dragon+3c
This article is not about a proof that P = PSPACE. That would be way bigger news since it also directly implies P = NP.