For Algorithms, a Little Memory Outweighs a Lot of Time

upstart writes:

For Algorithms, a Little Memory Outweighs a Lot of Time:

One of the most important classes goes by the humble name "P." Roughly speaking, it encompasses all problems that can be solved in a reasonable amount of time. An analogous complexity class for space is dubbed "PSPACE."

The relationship between these two classes is one of the central questions of complexity theory. Every problem in P is also in PSPACE, because fast algorithms just don't have enough time to fill up much space in a computer's memory. If the reverse statement were also true, the two classes would be equivalent: Space and time would have comparable computational power. But complexity theorists suspect that PSPACE is a much larger class, containing many problems that aren't in P. In other words, they believe that space is a far more powerful computational resource than time. This belief stems from the fact that algorithms can use the same small chunk of memory over and over, while time isn't as forgiving - once it passes, you can't get it back.

"The intuition is just so simple," Williams said. "You can reuse space, but you can't reuse time."

But intuition isn't good enough for complexity theorists: They want rigorous proof. To prove that PSPACE is larger than P, researchers would have to show that for some problems in PSPACE, fast algorithms are categorically impossible. Where would they even start?

Read more of this story at SoylentNews.