For algorithms, a little memory outweighs a lot of time
quantamagazine.org
For algorithms, a little memory outweighs a lot of time
1–10 of 144 posts
Re: For algorithms, a little memory outweighs a lot of time
#2[dead]
Re: For algorithms, a little memory outweighs a lot of time
#3Minus the fuzz: A multitape Turing machine running in time t can be simulated using O(sqrt(t log t)) space (and typically more than t time).
Re: For algorithms, a little memory outweighs a lot of time
#4I 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.
Re: For algorithms, a little memory outweighs a lot of time
#5I 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.
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.
Re: For algorithms, a little memory outweighs a lot of time
#6I 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.
[deleted]
Re: For algorithms, a little memory outweighs a lot of time
#7I 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.
But you also spend time on updating cells, so it is not that intuitive.
Re: For algorithms, a little memory outweighs a lot of time
#8I 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.
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.
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....
Re: For algorithms, a little memory outweighs a lot of time
#9I 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.
But you also spend time on updating cells, so it is not that intuitive.
I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes.
More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.
Re: For algorithms, a little memory outweighs a lot of time
#10Earlier quoted context omitted.
Intuitive yes, but since P != PSPACE is still unproven it's clearly hard to demonstrate.
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....
This article is not about a proof that P = PSPACE. That would be way bigger news since it also directly implies P = NP.