<p>By the <a href="http://en.wikipedia.org/wiki/Space_hierarchy_theorem" rel="nofollow">Space Hierarchy Theorem</a>, for every <a href="http://en.wikipedia.org/wiki/Space-constructible_function" rel="nofollow">space-constructible</a> space bound $s&gt;\log(n)$, there is a problem $L \in \mathsf{SPACE}(s)\setminus \mathsf{SPACE}(o(s))$. </p>

<p>In other words, $L$ can be solved in space $s$, and thus in time $c^{s(n)}$, but not in space $o(s)$, <em>regardless</em> of how much extra time you allow.</p>

CC BY-SA 3.0
2012-09-05T17:37:39.097Z
This does not seem to answer the question?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-09-05T11:13:33.397Z
2012-09-05T11:13:33.397Z
Radu Curticapean
<p>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. </p>

CC BY-SA 3.0
2012-09-05T17:18:47.357Z
2012-09-05T17:18:47.357Z
Suresh Venkat
<p>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.</p>

<p>If there is such a function, please show one.</p>

CC BY-SA 3.0
2012-09-05T18:29:09.520Z
First and second sentence seem to ask different questions.
Kaveh
<cc.complexity-theory><time-complexity><space-complexity>
Function with space-depending computation time
Michal Zajac
# Function with space-depending computation time

(Asked by: username_0 on 2012-09-05)

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.

**Tags:** cc.complexity-theory, time-complexity, space-complexity

> **Comments:**
> **username_1**: First and second sentence seem to ask different questions.  

---

## 2 answers

### Answer by username_2 on 2012-09-05. Score: 4

By the [Space Hierarchy Theorem](http://en.wikipedia.org/wiki/Space_hierarchy_theorem), for every [space-constructible](http://en.wikipedia.org/wiki/Space-constructible_function) 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.

> **Comments:**
> **username_3**: This does not seem to answer the question?  

---

### Answer by username_4 on 2012-09-05. Score: 0

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.


---

