# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

350 questions
Filter by
Sorted by
Tagged with
174 views

### More details on a language decided in $\Theta(\log \log n)$ space

In Language with $\log \log n$ space complexity?, the following non-regular language is described: $$L = \{b(0) \# b(1) \# \dots \# b(2^k-1) \mid k\in \mathbb{N}\}$$ where $b(i)$ is the $k$-bit ...
677 views

### Why isn't TQBF part of the polynomial hierarchy?

TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$. So given a formula in TQBF, shouldn't there be a level of the polynomial hierarchy that solves it? I think this is ...
73 views

### The complexity of BDD Synchronous Composition

As shown in Byrant's original paper, the time complexity of (single-variable) composition algorithm is cubic, and it is a tight upper bound. My question is about synchronous composition, written as ...
1k views

### Check for balanced parentheses in an expression in log-space

Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression. For ...
113 views

### What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)?

What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)? Is it O(n) because the maximum stack size is n, or is it O($n^2$) because there are $n(n+1)/2$ memory ...
750 views

### Why is PH in PSPACE?

$PH \subseteq PSPACE$. In order to prove it, one has to show that for a language $A \in \Sigma_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M_A$ that decides it in polynomial space....
34 views

### L contains the concatenations of all k-bit long strings. Why is it decided in PSPACE(loglogn)?

(This exercise is from Computation Complexity: A Conceptual Perspective by Oded Goldreich): For any k $\in \mathbb{N}$, let $w_k$ denote the concatenation of all k-bit long strings (in lexicographic ...
42 views

### The class of languages that can be certified in a small amount of space

NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time. I wonder, if we consider the same notion but ...
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 ...