Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at least $n^2$ (where $n$ is the length of the input) and is NP-hard when there is only linear space.
If there is such a function, please show one.
By the Space Hierarchy Theorem, for every space-constructible space bound $s>\log(n)$, there is a problem $L \in \mathsf{SPACE}(s)\setminus \mathsf{SPACE}(o(s))$.
In other words, $L$ can be solved in space $s$, and thus in time $c^{s(n)}$, but not in space $o(s)$, regardless of how much extra time you allow.
In the world of streaming, there are many problems that are easy to compute with linear space and impossible (not just hard) for sublinear space. For example, computing the most frequent element of a stream exactly is impossible without linear space via communication complexity lower bounds.
