# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

326 questions
Filter by
Sorted by
Tagged with
94 views

### What does $L$-uniformity mean?

I've understood that $L$-uniformity means that there's a TM that can output the description of $C_n$ in $O(\log n)$ space. Now, that seems odd to me since the description itself (as far as I ...
105 views

### Reachibility between first and last layer in grid graph in logspace

I am trying to prove that there exists logspace deterministic Turing machine that check if exists path between first row and last row in grid graph. Grid graph is matrix of $0s$ and $1s$, the ...
241 views

### What if there is a polynomial-time algorithm to minimize NFA?

Knowing that NFA-minimization has been proven to be P-SPACE complete, what if there is a polynomial-time algorithm to minimize NFA? Does that imply that P = PSPACE?
71 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 ...
100 views

### Complexity of emptiness checking for visibly pushdown automata?

Visibly pushdown automata [1] are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness ...
218 views

I understand that many algorithms have space/time tradeoffs-that is, to run faster, you can do things like caching data, which reduces time taken in exchange for space consumed. Given conservation of ...
431 views

### Is PSPACE closed under the following forall-there-exists construction?

Suppose I have a language $L$ (over alphabet $\Sigma$), such that $$w \in L \iff (\forall x \in \Sigma^*) (\exists y \in \Sigma^*) P(x,y,w).$$ and I can give a turing machine that decides $P(x,y,w)$ ...
3k views

### How to avoid loops/cycles in iterative deepening with linear space?

Breadth first graph search adds states that have already been visited to an explored set to avoid getting stuck in loops and cycles. This is fine since breadth first search needs exponential space to ...
518 views

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 ...
219 views

### Is Not-STCON is NL-Complete?

$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$ $Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$ I've tried the following proof: Let $S\in NL$, and ...
92 views

### Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$). Why do we have these ...
137 views

### Hamming numbers for $O(N)$ speed and $O(1)$ memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory. Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers. Is ...
90 views

### Space complexity of Horner's method

Following is the excerpt from wiki If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately $2n$ times the number of ...
48 views

### Replacing n with 2n in asymptotic bounds

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
439 views

### Membership problem for context sensitive languages PSPACE-complete

I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself. Let's mark the membership problem for CSL as MEM. First I have to ...
492 views

### Verifiers equivalent classes

This is a HW question, so Im not expecting full solutions or anything, but would love some direction. Also English is not my first language, so I apologize in advance. We define a new class of ...
72 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$)
2k views

### Show Recognizing two Regular Expressions as equal is in PSPACE

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{$R$and$S$are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ? What I know so far is that there are decidable ...
928 views

### Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
60 views

### (Why) is there no complexity class for linear space (O(n))? [duplicate]

tldr: I'm looking for any general information about the linear space complexity class. e.g. is there a complete problem for it? the Quantified Boolean Formula (QBF) problem is a P-space complete ...
Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...