A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time.

Is this true or false? and why? any idea?


closed as unclear what you're asking by Evil, fade2black, Yuval Filmus, David Richerby, cody Dec 7 '17 at 16:16

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ The question in the title differs from the question in the body. Which are you interested in? $\endgroup$ – Yuval Filmus Dec 1 '17 at 7:12
  • 3
    $\begingroup$ The answer depends on your model of computation. Which model of computation are you using? Turing machines? RAM machine? C programs? $\endgroup$ – Yuval Filmus Dec 1 '17 at 7:12

This depends on how precisely the words are meant.

In computer science, we often lack perfect (or even good) information about the behavior of algorithms. As a result, we tend to approximate or create upper bounds and talk about those instead of actual behavior. In most contexts, when you say “the algorithm requires superpolynomial space” what you mean is that in the worst case, we cannot prove that the algorithm uses less than superpolynomial space.

This is very different from the literal interpretation of your words, where an algorithm requires superpolynomial space if there exists an input for which it use superpolynomial space.

So why does this matter? Writing $k$ units of space generally requires at least $k$ units of time in the contexts where we are interested in doing space analysis. Therefore if the algorithm in fact requires superpolynomial space, it must require superpolynomial time. Additionally, if we cannot prove it doesn’t require superpolynomial space, then it follows that we cannot prove that it doesn’t require superpolynomial time. However, it is possible for us to not be able to prove that it doesn’t require superpolynomial space and in fact requires polynomial time.

Additionally, it’s possible that in your context writing $k$ units of space can be done in much less than $k$ time. There do exist computation models where space is much cheaper than time in this sense, but in those contexts we rarely care about space complexity, because it’s so cheap.

So, the answer in most contexts is no, but it’s very important to think carefully about what your words mean.


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