Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

67 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
38 views

Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?

I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now ...
0
votes
0answers
52 views

Relationship between SPACE(t(n)) and DTIME(t(n))

I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes $DTIME(n)$ $DTIME(n^2)$ $DTIME(2^n)$ $DTIME(2^{2^n})$ $...
0
votes
0answers
50 views

Space complexity for accepting word decision problem of DFAs

It is well known that the the decision problem $w \in \mathcal{L}(M)$ for a DFA $M=(Q,\Sigma, \delta, q_0,F)$ is in $\mathcal{O}(|w|)$. To proof this we assume that the successor state computation can ...
0
votes
1answer
495 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'. ...
0
votes
0answers
275 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://...
0
votes
0answers
120 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
0answers
102 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
0answers
66 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 ...
0
votes
0answers
154 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.
0
votes
0answers
143 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 ...
0
votes
0answers
68 views

P-complete problem due to logspace reductions. What does it mean?

Prove that problem $A$ is complete in $P$ due to reductions computed in logarythmic space How to understand this statement ? What should be shown ? For me: 1. $A$ is in $P$. 2. Each problem in $...
0
votes
0answers
112 views

Convert conjunctive normal form to equivalent boolean formula with only NOR gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NOR gates with ...
0
votes
0answers
98 views

Is the algorithm to solve 4SAT correct and what it's both time and space complexity?

The algorithm works as follows: For each clause, the algorithm turns the middle disjunction into conjunction, i.e. if an arbitrary clause is of the form: (l1 ∨ l2) ∨ (l3 ∨ l4) Then after ...
0
votes
0answers
64 views

Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$

If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$ If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$ What I tried: Since it's impossible to show that $EXP \subseteq EXP^A$ because: We ...
0
votes
0answers
118 views

Is there a fundamental concept underlying trade-offs in CS and are they unavoidable?

There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching ...
0
votes
0answers
342 views

What is the time and space complexity of unidirectional bfs and bidirectional bfs?

How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?
0
votes
1answer
87 views

Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem

We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says: Let $L\in NPSPACE$. Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that ...

1
2