Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
1
vote
1answer
47 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
194 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
231 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
124 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
34 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
76 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
134 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
43 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
100 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
250 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
149 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
580 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
452 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
146 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
177 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
31 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
47 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
43 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
119 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
186 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
92 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
140 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
46 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
92 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
69 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
192 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
59 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
245 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
151 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
57 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
193 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 ...
2
votes
1answer
333 views

How to prove that $n\log n$ is space constructible?

I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that ...
6
votes
1answer
1k views

Does space complexity analysis usually include output space?

Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this ...
0
votes
0answers
120 views

Proving SAT is in L

How to prove that SAT is in L if and only if NP=L? I know that reducing SAT in cook-levin theorem is computable in deterministic linear space . How to do it in log space? Any reference will also help.
1
vote
1answer
26 views

What is the relationship between the complexity class $L^n$ and $NL^m$?

The space hierarchy theorem shows that $$\mathrm{\mathbf{L}}^{1} \subsetneq \mathrm{\mathbf{L}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{L}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{...
1
vote
2answers
98 views

Is $2^n$ steps enough to tell if DTM will run forever?

In the space hierarchy theorem proof for PSPACE from Wikipedia, we reject the input after $2^{|f(x)|}$ steps on the machine $M$, reportedly to avoid infinite running time. My question is: how is it ...
2
votes
1answer
710 views

What algorithm to use for this subset sum problem

I have a typical subset sum problem and I'm looking to choose the proper algorithm to solve it, the set contains (around) 1000 elements, and elements are constrained to max 22 bits for now. I have ...
3
votes
2answers
584 views

How to compare algorithms having the same complexity

I am new to programming and want to learn how to compare algorithms having the same complexity and pick the best one. Certain problems can be sloved using several algorithms which have the same ...
0
votes
0answers
129 views

Alternating Turing Machine: Why one cannot generalize the proof of AL = P?

In their paper "Alternation" Chandra et al. show how an Alternating Turing Machine can simulate a Deterministic Turing Machine with time-complexity $t(n)$ using only $\log(t(n))$ space what implies $P ...
2
votes
1answer
600 views

STCON is NL complete - but why is the reduction in L?

I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity I understand the reduction, but how is it logspace? I understand each state is of $O(\log(n))$ space....
4
votes
1answer
167 views

$UCYCLE$ is in $L$

I'm trying to understand the log-space algorithm for $$UCYCLE = \{ \langle G \rangle \ | \text{ $G$ is an undirected graph containing a cycle} \}$$ The basic idea is traversing from every $v\in V$, ...