Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
0
votes
1answer
274 views

Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
3
votes
1answer
49 views

Graphs in space efficient representation

Let $G$ be a graph such that $V$ denotes a vertex set and $E$ is an edge set of the graph $G$. Let us consider that for the input graph $G$ it is the case that $|E| \le O(|V| \log |V|)$. Given a graph ...
1
vote
0answers
48 views

If problem A is logspace reducible to 2-SAT, is A in NL?

I'm trying to prove that some problem, A, is in NL. I have found a logspace reduction from A to 2-SAT - am right in thinking that this is not sufficient to prove that A is in NL? If so, how does one ...
1
vote
0answers
24 views

How to check a graph diameter in LOGSPACE?

Given a graph G, how can I check that its diameter doesn't exceed log(n) (n is the number of vertices)- by using only O(log(n)) space? (adjacency matrix doesn't seems to help...)
1
vote
1answer
174 views

Relation beetween log-space reduction and polynomial time reduction

I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the ...
0
votes
1answer
23 views

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?

What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
1
vote
0answers
192 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
3
votes
2answers
8k views

Time and space complexity of Radix sort

I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the ...
0
votes
2answers
119 views

Data structure for finding max, inserting and deleting in O(1) and O(n) space

This is an interview question. I need to implement a data structure that supports the following operations: Insertion of an integer in $O(1)$ Deletion of an integer (for example, if we call delete(7),...
1
vote
0answers
37 views

What does actually happens on tile hashing

I am going through Richard Sutton book about Reinforcement Learning and I just encountered the tile coding method. I understood pretty well the principles, however, at the very end of the section, ...
1
vote
1answer
51 views

Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$

I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$. The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that ...
0
votes
0answers
209 views

Space complexity of Coin change with memoization

I've read conflicting answers for the space complexity of the top down implementation w/ memoization for the classic coin change problem. Would this be O(N * M) space as Interview Cake says https://...
1
vote
2answers
267 views

Is every regular/context free langauge decidable in LogSpace?

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
4
votes
1answer
137 views

Why not polynomial-space reductions for $PSPACE$-hardness?

A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le_p L'$. Here $L \le_p L'$ means that $L$ is polynomial-time reducible to $L'$. Why does we use time reductions instead of ...
2
votes
1answer
36 views

Exponential Space Complexity equality

Consider $$ \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE}(2^{c (\log{n})^2}) \quad \overset{?}{=} \quad \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE} ( n^{c \log{n}})$$ My lecture notes say that this is ...
1
vote
1answer
84 views

Does Multitape reduction to a one tape machine preserve space complexity?

Suppose a Turing machine $M$ has a read-only input-tape and $k$ read-write work-tapes whose non-blank cells are each bounded by $f(|x|)$ where $|x|$ is the length of the input. Is there some constant ...
4
votes
1answer
152 views

Problem with understanding proof of the Space Hierarchy Theorem

The Space Hierarchy Theorem states that If $f(n)$ is space contructible, then for any $g(n) \in o(f(n))$ we have $SPACE(f(n)) \neq SPACE(g(n))$ An example of a SHT proof can be found here or here ...
2
votes
1answer
44 views

In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?

In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex ...
2
votes
1answer
89 views

What is tight NSPACE complexity of $ALT\text{-}SPACE(a(n),s(n))$?

According to Ryan Williams's answer $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(a(n)\log n)$. Does there exist any better bound (for example something like $ALT\text{-}SPACE(a(n),\log n)\...
1
vote
2answers
42 views

STCON in L using matrix multipication algorithm?

I'm trying to understand why the following is incorrect. Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-...
3
votes
1answer
103 views

Is $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$?

We know that $\mathsf{DSPACE}(\log\log n) = \mathsf{DSPACE}(1)$ according to this proof. Can we claim that $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$ or something like $\mathsf{DSPACE}(n^3)=\...
3
votes
1answer
276 views

Does the space complexity of a recursive algorithm depend on the total no of recursive calls?

I am confused whether space complexity of a recursive algorithm depends on the total number of recursive calls or not. Say I have an algorithm which has exponential function calls, but stack size is ...
3
votes
1answer
51 views

Connecting strings in a graph is a PSPACE problem

We define the following problem as: Let $M$ be a TM with alphabet $\Gamma$, with $\{a,b,$ #$\} \subset \Gamma$. We define, for every natural number $n$ the graph $G_{M,n}$ by: $V_{M,n} = \{a,b\}^n$,...
0
votes
2answers
65 views

Why it is not $O(m)$ but $O(\log m)$?

I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2. Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$. ...
0
votes
1answer
45 views

A Language Belonges to PSPACE

Let $A,B$ be two languages, for which we know: $A \in PSPACE$ $A\le_LB$ Can we conclude from the above that $B \in PSPACE$ ? I think the answer is no, however I don't know how to ...
1
vote
1answer
171 views

$MIN_{NFA}$ is PSPACE complete

The problem is taken out of Theory of Computational Complexity: Now, I think I've successfully proven that $ALL_{NFA} = \{(A) : A$ is an NFA and $ L(A) = \Sigma^*\} \leq_p MIN_{NFA}$. Which implies ...
3
votes
1answer
640 views

Fast, stable, almost in-place radix and merge sorts

I've developed LSD radix sort algorithm that is stable, about as fast as the classic LSD radix sort, require only $O(\sqrt{RN})$ extra space when we sort into R buckets. The same technique also ...
1
vote
2answers
480 views

Show that NP is not equal to SPACE(n)

I want to show that $\text{NP} \neq \text{SPACE}(n)$ and tried it like this: Let $L$ be in $\text{SPACE}(n)$ so there is a deterministic $k$-tape TM which decides $L$ in polynomial time. Let's ...
1
vote
1answer
166 views

What is a space constructible function?

I've searched this and was not able to understand the answer. What's the idea/intuition behind this? What's the purpose and why is it important? And considering the wikipedia explaination, ...
1
vote
2answers
185 views

Space/Time Hierarchy Theorem - proving the language of the machine is in the larger space class

I am trying to understand the space and time Hierarchy theorems according to Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach but the more general case. What I don't ...
1
vote
0answers
32 views

EXPTIME $\neq$ EXPSPACE consequences?

We know that $EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE$, where $EXPSPACE = DSPACE(2^{poly(n)})$. Question: Is known any consequences of $EXPTIME \neq EXPSPACE$? (nothing in complexity zoo or wikipedia)
2
votes
0answers
56 views

Why is a pointer constant space?

If a pointer specifies a point in memory, would the amount of space a pointer takes not be dependent on how much memory it could possibly range over? So for example, if we have 4 locations of memory ...
2
votes
1answer
45 views

Is it known that $AC^1 \subseteq L$?

A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ ...
1
vote
1answer
121 views

Why is DTIME(n) not equal to NP, and consequently, DSPACE(n) not equal to NP?

Intuitively it would seem like these equalities are false since DTIME(n) and DSPACE(N) are in terms of deterministic Turing machines and NP is non-deterministic, but I'm struggling to come up with a ...
2
votes
1answer
197 views

Is every PSPACE-complete problem complete with respect to logspace reductions?

A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$, $$ A \le_L ...
2
votes
1answer
98 views

Space complexity of boolean circuit evaluation

I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size. Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$. Now, assuming the fan in of ...
3
votes
1answer
144 views

Does the circuit value problem require only log space in alternating Turing machines

Why does the circuit value problem run in log space on an alternating Turing machine? It is claimed to be so in my university's lecture notes. Also, it is claimed that monotone circuit value problem ...
2
votes
0answers
47 views

Proving that the sum of DTIME and DSPACE are not equal

I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$. There isn't a solution provided in the textbook. I've been working with a solution ...
0
votes
0answers
95 views

show doubly connected graph is NL complete

The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
0
votes
1answer
95 views

Space complexity for connectivity problem with given graph diameter

Given $(G,D,d)$, a graph, the graph diameter and the maximum outdegree of the graph. Verify that $G$ is strongly connected in $O(D\log d + \log n)$ space complexity. I thought about using the $STCON$ ...
0
votes
0answers
74 views

Generalized Geography problem time and space complexity

We all know the algorithm that solves the Generalized Geography problem using polynomial space (it's described on wiki). My question is: what is the time complexity of this algorithm? I'd like a more ...
0
votes
1answer
51 views

Show that an NP-Complete problem exists that is contained in SPACE(n)

The problem I am working on is the following: Show that there exists an $NP$-Complete problem in $SPACE(n)$. Does the existence of such a problem imply that $NP$ is contained in $SPACE(n)$. Why ...
-2
votes
5answers
226 views

Algorithm to generate non-repeating random numbers of O(1) memory?

Is it possible to create $O(1)$ memory consuming algorithm, which is generating non-repeating pseudo random numbers? I can remember numbers in the hash set and it will be $O(1)$ time, but the set ...
0
votes
0answers
62 views

Row-Column agnostic Matrix datastructure

Due to the linear nature of computer memory, row-major and column-major matrices have different performance for row- vs. column access. The obvious solution would be to keep two copies of the same ...
1
vote
1answer
262 views

How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space?

Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$ Prove that MULT $\in L$ How do I show that this language, MULT, is computable in Logarithmic space? Let us assume a#b#c ...
1
vote
0answers
24 views

United space-time complexity of finite strings

Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example ...
1
vote
2answers
125 views

Best way we know search for an integer

Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?" My ...
0
votes
1answer
180 views

PSpace-completeness under PSpace reductions

A language $L$ is PSpace-complete, if it meets two conditions: It is in PSpace. Every other PSpace-complete language reduces to it in polynomial time. Question: suppose we change the second ...
3
votes
1answer
59 views

Limited oracle TM

Let $M$ be a Turing machine with oracle to $B$ that can decide $B$ in polynomial time. In the general case it means nothing, since we can just pass the input as a query to the oracle of $B$ and accept/...
2
votes
0answers
202 views

Natural logspace complete problems

After Omer Reingold's famous proof (from 2005?) that SL = L, the distinction between natural L complete problems and natural SL complete problems has been mostly dropped, so that it became difficult ...