# Questions tagged [space-complexity]

The tag has no usage guidance.

62 questions
Filter by
Sorted by
Tagged with
2k views

### What are some algorithms where space complexity tends to be the limiting factor in practice?

Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? ...
865 views

### Best current space lower bound for SAT?

Following on from a previous question, what are the best current space lower bounds for SAT? With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a ...
3k views

### How much time to recognize palindromes in logarithmic space?

It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time ...
926 views

### What is the space complexity of calculating Eigenvalues?

I am looking for a survey paper or a book covering results about the space complexity of common linear algebra operations such as matrix rank, eigenvalues calculation, etc. I stress the "space ...
945 views

### Quadratic relationship between nondeterministic and deterministic space?

Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades. Suppose ...
741 views

### Is Quasi-polynomial time in PSPACE?

I had done some search on this but I was not able to find an answer either way. Huck answered it fully. Thanks :)
340 views

342 views

### Are space and time hierarchies even comparable?

I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such ...
169 views

160 views

### Is $L \subset 1NL$ when $L \neq NL$?

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
155 views

### Immutable Space Model

I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence? What is generally known about models of ...
364 views

### PSPACE completeness, with different kinds of reductions

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
265 views

### Is the primality problem with unary input NLOGSPACE-Hard?

Consider the language $L=\{1^n : n \text{ is prime}\}$. Is this language NLOGSPACE-Hard? The motivation for this question is that $L$ is a good candidate for reducing to other languages related to my ...
612 views

### What happens when PSPACE contains NEXP?

The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial). In the ...
185 views

### On space complexity of permanent modulo $2^t$?

We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current ...
845 views

### Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$. Are there any known connections between the problems: P vs L, UP vs UL, NP ...
877 views

### Does L=P imply any new complexity class separations?

If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L. I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly ...
178 views

### Is $UL\neq PSPACE$ known?

$L\neq DSPACE[\omega(\log n)]$ is known. Is $UL\neq DSPACE[\omega(\log n)]$ and $UL\neq PSPACE$ known?
189 views

### On complexity class $\mathsf{\Pi_2 L}$

I suggest the following definition of $\mathsf{\Pi_2 L}$ (similarly to the certificate definition of $\mathsf{NL}$): A language $L$ belongs to $\mathsf{\Pi_2 L}$ iff there exists a deterministic ...
367 views

### state-of-the-art bit complexity of the determinant

I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits. I would like to know what is the state-of-the-...
311 views

### Satisfiability for various branching programs

Clearly, SAT for CNF, formula, or many classes of boolean circuits have strong significance on the entire theory community. Branching program, or BDD is one of the most basic and popular computational ...
169 views

### Function with space-depending computation time

Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at ...
750 views

### Space complexity for multiplying $m$ matrices

Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$. The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. ...
236 views

### Low space computation and branching program

One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log T(n)]$. I ...
It is a major open problem whether $NL \subseteq SC$, or equivalently, whether directed reachability can be solved (simultaneously) in poly-logarithmic space and polynomial time. What is known ...