# Questions tagged [space-complexity]

The tag has no usage guidance.

62 questions
Filter by
Sorted by
Tagged with
192 views

### $CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?

Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$. Savitch provides $NL\subseteq L^{2}$. If $CH=UL$ we clearly got rid of the transitive closure bottleneck ...
126 views

### Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$

For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not ...
123 views

### Family of functions with properties similar to k-wise independent hash functions

I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
42 views

### Bipartite graph projections, with threshold

Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$. The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
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?
94 views

### Relationship between SC and NL

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

### Size of CNF Formula for Adjacency in Configuration Graph

Suppose $M$ is a (non-deterministic) TM that runs in space $S(n)$. Then, the configuration graph $G_{M,x}$ of $M$ on $x$ has size $2^{O(S(n))}$. Arora-Barak (see http://theory.cs.princeton.edu/...
64 views

### Reference to “compressibility” of logarithmic space [closed]

Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ...
175 views

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

### Is sliding blocks linear space complete?

Sliding blocks is PSPACE complete even in its simplest form involving 1x2 and 2x1 blocks (without rotation or fractional positions) in a rectangular area, with goal being to move a designated block to ...
180 views

### Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular ...
91 views

### Complexity status of restricted k-clique [closed]

Restricted $k$-clique: Input: $(G,v,k)$ where $v$ is vertex in $V$ Output: k-clique containing vertex $v$. What is the space and time complexity status of this Restricted $k$-clique problem? Is ...
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 ...
65 views

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

### Space complexity of integer programming

Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x_1,\dots,x_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a ...
296 views

### Is bounded-width SAT decidable in logspace?

Elberfeld, Jakoby, and Tantau 2010 (ECCC TR10-062) proved a space-efficient version of Bodlaender's theorem. They showed that for graphs with treewidth at most $k$, a tree decomposition of width $k$ ...
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 ...
169 views