Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

385 questions
Filter by
Sorted by
Tagged with
24 views

Is $DSPACE(n^8) \subset NSPACE(n^5)$?

I encountered this problem which asks whether $DSPACE(n^8) \subset NSPACE(n^5)$ is sure to hold. I know from Savitch's Theorem that: $$NSPACE(n^5) \subseteq DSPACE((n^5)^2) = DSPACE(n^{10})$$ If the ...
17 views

proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

I came across this problem which asks to prove: $$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$ for $S(n) \geq \log{(n)}$, with $S(n)$ being fully time-constructible... As an attempt, isn't the proof ...
25 views

Does this algorithm traverse trees in logspace?

Does this algorithm traverse trees (correctly) in logspace? Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
41 views

Prove that all regular language is in L

im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space). I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all ...
33 views

$\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
19 views

Does this imply Hamiltonian path cannot be decided in nondeterministic logspace?

Suppose I nondeterministically walk around in a graph with n vertices. When looking for a Hamiltonian path, at some point I’ve walked n/2 vertices. There are (n choose n/2) different combinations of ...
33 views

Does this imply checking a candidate Hamiltonian Path solution can be done in logspace?

Assume vertices are integers base 2. Smallest vertex is 1. There are n vertices. Our input is: the number of vertices (n expressed in log(n) bits - ...
31 views

Algorithm to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$

We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of ...
43 views

Why is $DSPACE(\log(n)) = NSPACE(\log(n))$ not known?

Here $DSPACE(\log(n))$ is the family of algorithms for which there exists a deterministic Turing machine using $O(\log(n))$ space. On the other hand $NSPACE(\log(n))$ is the family of algorithms for ...
35 views

Are polynomials in one variable logspace-computable?

Given a polynomial function $$p\quad=\quad \lambda\, x\in\mathbb{N}_0.\ \sum_{i=0}^n a_i x^i$$ with $a_i\in\mathbb{Z}$ for all $i\leqslant n$, can you compute $p$ by a logspace transducer if the input ...
118 views

Logarithmic reduction from Clique to Half-Clique

so the question is in the title basically but I am now studying for a Complexity Theory Exam and encountered this problem in the exercises. I understand how to make a poly-reduction but I am not able ...
38 views

53 views

69 views

211 views

What is the time and space complexity of the algorithm to either prove or refute that given expression is equals to (A+B)^n for any natural number n [closed]

Note that this is not duplicate of my previous question: how to simplify algebraic expressions, though it is similar, but still this is different, this is not the same. I need an algorithm that ...
223 views

Find the 10 top most occurring strings in a huge array of objects

Find the 10 top most occurring strings in a huge array of Strings. Since the array is huge, it is not possible to load it in memory completely. My idea is to parse the arrays one by one and put the ...
71 views

The existence of a cycle in a directed graph is a NL-complete? [duplicate]

Show that the problem of the existence of a cycle in a directed graph is a $NL-complete$ problem. I have already successfully demonstrated that this problem $\in NL$. But I'm stuck on how to take it ...
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 ...