# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

338 questions
Filter by
Sorted by
Tagged with
80 views

### Quick and space-efficient way to find whether two sets intersect

I hope you can help me - Given a lot of sets containing integers, I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect. Note that I don'...
98 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$ ...
55 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 ...
93 views

### Relating memory complexity and decidablity

Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a ...
74 views

### PSPACE and DTIME $2^{cn}$

This is a HW question that I'm stuck on and was hoping for some help. we're supposed to prove that: PSPACE not equals DTIME($2^{cn}$) for every $c>0$ (or actually for the union of all $c>0$)
62 views

### Memory Requirement for a Computable Problem

I was thinking whether it is true that every computational problem intrinsically has a minimum ammount of memory required for any algorithm that computes it. But then i was confused to what "memory ...
48 views

### Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)

The solution to this problem can be found here. It says: To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of ...
31 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 ...
32 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 ...
101 views

### Maximum space consumption of stack and queue for DFS and BFS

I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS. Since BFS and DFS while traveling graphs have ...
39 views

### Can you determinize an NFA in PSPACE?

QUESTION Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$? MORE DETAILS I'm asking this as I want to be able to ...
60 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 ...
49 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 ...
34 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 ...
22 views

I was wondering if anyone could point to some sort of review to this paper "Table Design In Dynamic Programming" by Peter Steffen and Robert Giegerich? https://dl.acm.org/citation.cfm?id=1182768 Has ...
45 views

51 views

186 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 ...
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 ...