# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

342 questions
Filter by
Sorted by
Tagged with
10k views

...
812 views

### Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly ...
157 views

### 'Stones' game complexity

I'm trying to find complexity class of finding winning strategy for first player in following game: Intance of 'Stones' game is: finite set $X$ relation $R \subseteq X^3$ set $Y \subseteq X$ and ...
161 views

### Proving language in Space Complexity

I'd like to know if I have the right intuition and my answer is headed the correct way. I am given a function $f = \{0, 1\}^* \rightarrow \{0, 1\}^*$ that is computable in space $O(\log n)$ assume ...
579 views

### Proving that Turing Machine M runs in time $O(2^{dn})$

I'm trying to solve this question in order to review for my exam, and this one has got me a bit stumped. From the looks of it, it seems like a fairly straight-forward question, but I can't figure out ...
76 views

### Showing transitivity of PSPACE?

For the following question: If B is an element of PSPACE and A is an element of PSPACE-Complete, and A polynomial reduces to B, then B is an element of PSPACE-Complete. I am trying to prove this, ...
734 views

### What is a compact way to represent a partition of a set?

There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly space-...
972 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 ...
326 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 ...
378 views

### Why does a polynomial-time language have a polynomial-sized circuit?

I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs ...
501 views

125 views

### Prove that 2-Colourability is in L from Undir-Reachability is in L

Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G? I need to prove that the 2-Colourability is in ...
147 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?
157 views

### NL- definition and a problem

The question is: What is the smallest complexity class in which the following problem is contained: Given a graph with $n$ nodes, Is there independent set of size of at least $n-10$? I have a little ...
493 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 ...
860 views

### Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity

Prove that the problem of determining if graph is bipartite is computationally equivalent under log-space reductions to $s$-$t$ undirected connectivity. Problem of $s$-$t$ undirected connectivity is ...
315 views

### Logarithmic space difference between deterministic and non-deterministic algorithms

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
683 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 ...
152 views

801 views

217 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 ...