Function with space-depending computation time 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&gt;\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.