Asymptotic analyses of the space needed to run algorithms.
4
votes
2answers
43 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 ...
3
votes
1answer
58 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 ...
1
vote
1answer
35 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, ...
5
votes
1answer
68 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 ...
5
votes
4answers
92 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 ...
6
votes
2answers
63 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 ...
2
votes
2answers
55 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 ...
-1
votes
1answer
96 views
Relationship between L and PSPACE
I have a question have to answer, so that, if anyone have the answer, please help me.
The problem is: Give a self-contained proof that $\mathsf{L} \neq \mathsf{PSPACE}$
where:
$\qquad \mathsf{L} ...
-1
votes
1answer
55 views
Book to learn Algorithm Complexity
I need a good book which starts from quite beginner to learn about calculating the complexity of Algorithm??
1
vote
2answers
46 views
Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete
I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete.
Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in ...
1
vote
1answer
45 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 ...
7
votes
1answer
81 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?
5
votes
1answer
66 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 ...
5
votes
1answer
231 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 ...
1
vote
1answer
39 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 ...
2
votes
0answers
60 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 ...
4
votes
1answer
105 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
63 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
49 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 ...
3
votes
1answer
71 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)$
...
4
votes
2answers
137 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?
2
votes
1answer
103 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 ...
2
votes
1answer
85 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
161 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 ...
4
votes
1answer
103 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 ...
0
votes
1answer
43 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 ...
3
votes
1answer
90 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
88 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 ...
6
votes
1answer
104 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 ...
3
votes
1answer
209 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,\: ...
0
votes
0answers
32 views
Function with space-depending computation time [closed]
I have a question of existence of a function which is easily computable for one space capacity and is hard to compute for another. That is, I am looking for a function which can be computed in ...
2
votes
2answers
140 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
...
5
votes
1answer
120 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 ...
5
votes
2answers
124 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 ...
9
votes
1answer
248 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 ...
3
votes
1answer
58 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 ...
4
votes
1answer
206 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 ...
6
votes
2answers
136 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
110 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 ...
11
votes
1answer
226 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 ...
1
vote
0answers
112 views
Optimal asymptotic space complexity after binary-tree compression? [closed]
What is the optimal asymptotic space complexity of a tree after binary-tree compression (without using probablistic techniques)?
E.g. from the (optimal?) techniques shown by Chen, Shenfeng, and John ...
8
votes
3answers
256 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 ...
