Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
2
votes
0answers
311 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 ...
5
votes
1answer
659 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 ...
2
votes
1answer
148 views

Power of Double - Logarithmic Space

I try to solve exercise "on the power of double - logarithmic space" from the great textbook Computational Complexity by Oded Goldreich. The goal is to show that the given set $S=\left \{ w_k \mid k \...
2
votes
1answer
87 views

Concluding $SPACE(n^2) \neq SPACE(n^7)$ from universal turing machine running time

Let $M_U$ be an universal Turing machine which fulfills the following condition: If $M$ running $x$ takes $f(x)$ space, then $M_U$ running on $\langle \langle M\rangle,x\rangle$ takes $(f(|x|))^3+2\...
3
votes
1answer
736 views

Equality of NSpace and coNSpace classes

I'm trying to decide which of the following statements are true: $\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$ $\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$ $\mathsf{NSpace}...
6
votes
2answers
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?
3
votes
1answer
2k views

Prove the following problem is NL-complete

Suppose $$A = \left\{\langle G, d, s, t\rangle \;\Bigg|\; \begin{array}{l} \text{\(G\) undirected}, \\ \text{\(s\) and \(t\) are nodes in \(G\)}, \\ \text{there is a path of length \(d\) from \(...
3
votes
1answer
320 views

Show that k-clique lies in L

The following exercise is difficult for me: Show that for each $k \in \mathbb{N}$ the question of existence of a $k$-clique within a graph lies in $\text{L}$. Hint: A $k$-clique denotes $k$ ...
4
votes
2answers
198 views

Show that the multiplication lies in FL

I don't know exactly how to solve the exercise below. Show that the multiplication lies in $\text{FL}$. Hint: A useful approach to a solution is to split the exercise into two parts and to ...
5
votes
1answer
483 views

Showing that Independent set of size $k$ can be decided using logarithmic space

An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of ...
4
votes
2answers
987 views

Time complexity for count-change procedure in SICP

In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem ...
4
votes
1answer
1k views

Relation between interactive proof systems (IP), NP, coNP, PSPACE

I would like to ask you some clarification on the following question: know that ${\sf NP}$ is a subset of ${\sf IP}$ and also ${\sf coNP}$ it is a subset of ${\sf IP}$. So ${\sf IP}$ is a biggest ...
3
votes
1answer
543 views

Proving that NPSPACE $\subseteq$ EXPTIME

I am following "Introduction to the theory of computation" by Sipser. My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE. $P \subseteq NP \...
7
votes
1answer
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 ...
5
votes
1answer
2k views

Minimum space needed to sort a stream of integers

This question has gotten a lot of attention on SO: Sorting 1 million 8-digit numbers in 1MB of RAM The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\...
2
votes
2answers
518 views

Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
11
votes
1answer
636 views

Bound on space for selection algorithm?

There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
9
votes
2answers
2k views

What's the complexity of Spearman's rank correlation coefficient computation?

I've been studying the Spearman's rank correlation coefficient $\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$. for two ...
14
votes
2answers
416 views

Time-space tradeoff for missing element problem

Here is a well-known problem. Given an array $A[1\dots n]$ of positive integers, output the smallest positive integer not in the array. The problem can be solved in $O(n)$ space and time: read the ...
5
votes
1answer
128 views

Complexity of space density and sequentiality

I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms. When we measure algorithms we tend to give the big-Oh notation ...
6
votes
1answer
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 (...
7
votes
2answers
632 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 ...
4
votes
2answers
714 views

Expected space consumption of skip lists

What is the expected space used by the skip list after inserting $n$ elements? I expect that in the worst case the space consumption may grow indefinitely. Wikipedia says space $O(n)$. How can this ...
14
votes
1answer
493 views

Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$

We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\...
10
votes
3answers
2k views

The space complexity of recognising Watson-Crick palindromes

I have the following algorithmic problem: Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes. Watson-Crick palindromes are strings whose reversed ...