<p>Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured bounds? </p>

<p>Are the bounds different if we require the new algorithm to also take $O(n^k)$?</p>

CC BY-SA 3.0
2015-03-11T21:58:23.307Z
Is “Let L” a universal quantifier, an existential quantifier, or something else? Likely there are such L computable in logarithmic space, and other L that require space at least $n^k/(\log n)^c$ or so (but we can’t prove either). Are you talking about lower or upper space bounds anyway?
Emil Jeřábek
CC BY-SA 3.0
2015-03-11T22:12:22.913Z
And while the question is unclear, it may or may not be answered by noting that the most efficient currently known simulation of time by space is the Hopcroft–Paul–Valiant theorem (anything computable in time $O(n^k)$ is computable in space $O(n^k/\log n)$).
Emil Jeřábek
<cc.complexity-theory><time-complexity><space-bounded>
What is the minimal known space for polytime algorithms
Josh F
# What is the minimal known space for polytime algorithms

(Asked by: username_0 on 2015-03-11)

Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured bounds?

Are the bounds different if we require the new algorithm to also take $O(n^k)$?

**Tags:** cc.complexity-theory, time-complexity, space-bounded
> **Comments:**
> **username_1**: Is “Let L” a universal quantifier, an existential quantifier, or something else? Likely there are such L computable in logarithmic space, and other L that require space at least $n^k/(\log n)^c$ or so (but we can’t prove either). Are you talking about lower or upper space bounds anyway?  
> **username_1**: And while the question is unclear, it may or may not be answered by noting that the most efficient currently known simulation of time by space is the Hopcroft–Paul–Valiant theorem (anything computable in time $O(n^k)$ is computable in space $O(n^k/\log n)$).  

---

## 0 answers

