4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ First and second sentence seem to ask different questions. $\endgroup$ – Kaveh Sep 5 '12 at 18:29
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.