# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

326 questions
Filter by
Sorted by
Tagged with
497 views

1k views

### NTIME(f) subset of DSPACE(f)

As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$? Can anyone point me to a proof or outline it here? Thanks!
494 views

### Is there an algorithm for algorithms time/space complexity optimisation?

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of ...
308 views

### Why is one often requiring space constructibility in Savitch's theorem?

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
487 views

### Bit complexity of O(1) time range query in a $k$-ary array

Consider the following problem: Let $k$ be a constant. We are given a $k$-ary array $A_{d_1\times\ldots\times d_k}$ of $0$ and $1$'s. Let $N = \prod_{i=1}^k d_i$. We want to create a data structure ...
640 views

### Complete Problems for $DSPACE(\log(n)^k)$

We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy? To be ...
2k views

### Has there been any more progress on P vs. PSPACE compared to P vs. NP?

I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown ...
146 views

### Does $\mathsf{NSPACE}( f (n)) = \mathsf{coNSPACE}( f (n))$ hold for $f(n) < \log (n)$?

It's known that for $f(n) \geq \log n$, $\mathsf{NSPACE}(f(n)) = \mathsf{coNSPACE}(f(n))$. What if $f(n)<\log n$? Are they also equal?
2k views

### Does space complexity analysis usually include output space?

Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this ...
293 views

### Can FPSPACE give exponentially long outputs?

I can't comment on this question, so I ask it here as a new question: Ricky Demer states there in a comment to the first answer "[...] since FPSPACE can give exponentially long outputs [...]" How ...
196 views

### Why do we reject turing machines that use space less than the log of the length of the input?

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the ...
216 views

### Simulate the concatenation of two log-space programs in log-space

I've got two log-space programs $F$ and $G$. Program $F$ will get input in array $A[1..n]$ and will create the output array $B[1..n]$. Program $G$ will get as input $B$ as created by $F$ and create ...
204 views

### Return copy of array, each element product of all others, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows: Given an array $<a_1, \ldots, a_n>$ of fixed-...
545 views

### Proof of APSPACE = EXP

I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book. Please give a semi-detailed proof of this. I have found a paper which has this proof(by ...
1k views

### Space complexity below $\log\log$

Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$. It's well known fact in Space Complexity, but how to show it explicitly?
262 views

### Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Definitions: An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
728 views

### Which CNF boolean formulas blow up exponentially at conversion to DNF?

If I'm correct, some boolean formulas in CNF require exponential size when being converted to an equivalent DNF version (and vice versa). But what is an example of such a formula (and is there a ...
1k views

### Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1

I have the following question from Computational Complexity - A modern Approach by Sanjeev Arora and Boaz Barak: [Q 4.1] Prove the existence of a universal TM for space bounded computation (...
9k views

### Space complexity analysis of binary recursive sum algorithm

I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books). It gives example of linear sum algorithm which uses linear recursion to calculate sum ...
708 views

### Prove or disprove that $NL$ is closed under polynomial many-one reductions

If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open ...
249 views

### TM recognizing $0^n1^n$ requires Ω(log n) space

I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space. I believe this can be ...
1k views

### How is the problem, {⟨G⟩|G has no triangle} in Logspace?

I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-...
662 views

### Are there strongly-polynomial algorithms that take more than polynomial time?

In [1] strongly-polynomial is defined as either: The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic ...
513 views

### Logic behind O(n) solution for 'Maximum length sub-array having given sum'

I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum (...
2k views

### How can an algorithm have exponential space complexity but polynomial time complexity?

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback ...
335 views

### Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?

When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, ...
944 views

### Space complexity for finding the minimum number outside the list of numbers

We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$. We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$. What is the ...
944 views

### Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
836 views

### Language with $\log\log n$ space complexity?

We know that every non-regular language can be recognized with $\Omega (\log\log n)$ space complexity. I'm looking for an example of a language which is $\Theta (\log\log n)$ space complexity (...
644 views

### Is DSPACE properly contained in NSPACE?

It may be a dumb question, but is $\mathsf{DSPACE}(f(n)) \subset \mathsf{NSPACE}(f(n))$ or is $\mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n))$? In other words, is the containment relation ...
11k views

### Memory complexity?

I am unclear about finding the memory complexity of an algorithm. Some places refer memory complexity as what container would be carrying for instance: ...
I want to prove that no PSPACE-complete problem is in NL using the space hierarchy theorem. What I want to say is this : From the time hierarchy theorem I know that for every $t(n)$ there exists a ...