# Tag Info

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

Most computations in algebraic geometry / commutative algebra. Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus ...
Accepted

### Quadratic relationship between nondeterministic and deterministic space?

In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that ...
Accepted

### The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

This situation comes up frequently in crypto, where you want to generate hard problem instances along with their solutions. For example, there is the work of Eric Bach (and later, Adam Kalai) on ...
Accepted

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

$\mathbf{UL}$ is contained in $\mathbf{NL}$, which is contained in $\mathbf{DSPACE}(\log^2 n)$ by Savitch's theorem, which is strictly contained in $\mathbf{PSPACE}$ by the space hierarchy theorem, so ...
Accepted

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

Indeed, using the resultss in Elberfeld-Jakoby-Tantau-2010 one can show that SAT can be decided in logspace on formulas whose incidence graph has bounded treewidth. Here is a sketch of how the main ...

### k-Vertex Cover problem is in parameterized Log space

Here is an algorithm that uses $2k^2 + O(\log n)$ space. This is just the observation that the well known "Buss kernel" for Vertex Cover can be computed in log-space: Say that a vertex has big degree ...
Accepted

### Are space and time hierarchies even comparable?

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$. For example, let $g(n) = n^3$ and f(n) = \begin{cases} n & \text{if $n$ is odd}, \\\ 2^{n^5} & \text{...

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

In knowledge compilation, the task is to compile some set $A\subseteq \{0,1\}^n$ into a format such that various queries can then be answered in polynomial time. For example, you can "compile&...

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

My go-to answer for this (the one I use in undergraduate algorithms classes) is the Bellman–Held–Karp dynamic programming algorithm for the traveling salesperson problem (https://en.wikipedia.org/wiki/...
Accepted

### Does the space hierarchy theorem generalize to non-uniform computation?

One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching ...

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

Dynamic programming is probably a general case of this but one specific, practically relevant and illustrative example is (global) pairwise sequence alignment using the Needleman–Wunsch algorithm, ...
Accepted

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

If I got this right, $\Pi_2L$ as defined above is equal to co-NP. The co-NP-complete DNF tautology sits in $\Pi_2L$: Use z for the assignment and y to choose which clause to check. To show $\Pi_2L$ in ...
Accepted

Accepted

### Best current space lower bound for SAT?

Looks like the best bound known (for multitape Turing machines) is logarithmic. Suppose $\delta\log n$ bits of binary worktape is enough to decide whether any $n$-bit CNF formula is satisfiable, for ...
Accepted

### Can Quarter-Subset Membership be decided space-efficiently?

I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be ...

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

A look-up table algorithm is the extreme example of an algorithm where space is the limiting factor. In these types of algorithms you have an entry in a table for every possible input. This results in ...
Accepted

### What is best known space requrement for solving SATISFIABILITY problem in exp time

If I understand your question correctly, as far as I understand this is computational-model dependent. An excellent lecture on the subject by Prof. Ryan O'Donnell can be found here: https://www....
Let $m = 1 + \log \ell$. Identify a hash function $h \colon \{0, 1\}^k \to \{0, 1\}^m$ with its $n$-bit truth table $h \in \{0, 1\}^n$ where $n = m \cdot 2^k$. Our hash family \$\mathcal{H} \subseteq \{...