# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

375 questions
Filter by
Sorted by
Tagged with
480 views

### Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

This question is related to my previous question: Looking for a set implementation with small memory footprint I'm looking for information about combined data structures, which can efficiently ...
87 views

### Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$

I need help with the following: Let $k\in \mathbb{N}$, define: $L^k=DSPACE(O(log^k(n)))$ $NL^k=NSPACE(O(log^k(n)))$ and: $PolyL=\bigcup_{k=1}^{\infty}L^k$ $PolyNL=\bigcup_{k=1}^{\infty}NL^k$ I need ...
544 views

### Why is it necessary to use binary numbers in logspace?

I have noticed that a lot of problems that are in L and NL use binary numbers. I don't understand why this is the case. Does a TM use less space by storing a binary number, than a "normal" one. In my ...
141 views

### How to show that FPATH is in NL?

Consider this problem: $\qquad\displaystyle \mathsf{FPATH} = \{\langle G, a_1,\dots,a_n\rangle \mid G \text{ is a digraph with directed path } (a_1,\dots,a_n)\}$ It's allowed to visit nodes outside ...
245 views

1k views

### The crux of Savitch's Theorem

In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going ...
1k views

### How to Study Space Complexity

I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially ...
1k 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 (...
144 views

### ALL_{REGEX} in PSPACE algorithm

$ALL_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^*$. In a proof for $ALL_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ ...
2k views

### Relation of Space and Time in Complexity?

I'm looking for some clarification on some concepts/facts I came across while studying for a class. I was reading the following wikipedia article. The below specific section and statement intrigued ...
574 views

### Logspace Transducer

I know that a logspace transducer is a deterministic Turing machine that enables us to use log-space complexity. I do not understand though why that is correct. Whatever algorithms can be implemented ...
2k views

### Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with operations ...
729 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 ...
314 views

655 views

### Known bounds on space complexity of multiplication decision problem

Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible to check in $O(1)$ ...
13k 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: ...
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!
886 views

### Set combination data structure (And storage complexity)

I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place. I have a problem where I am required to associate unique combinations from a set (unique ...
363 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, ...
11k views

...
837 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 ...
161 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 ...
180 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 ...
625 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, ...
807 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-...
1k 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 ...
349 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 ...
417 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 ...
655 views

129 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 ...
151 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?
159 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 ...
### 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 ...
### 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 ...