# Tag Info

## Hot answers tagged space-complexity

19 votes

### 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 ...
• 35.8k
19 votes
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 ...
• 6,898
15 votes
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 ...
• 26.5k
11 votes
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 ...
• 1,733
10 votes
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 ...
10 votes

### 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 ...
• 3,236
10 votes
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{...
• 2,718
8 votes

### 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&...
• 1,714
8 votes

### 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/...
• 50.3k
7 votes
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 ...
• 1,733
7 votes

### 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, ...
6 votes
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 ...
• 8,546
6 votes
Accepted

• 811
3 votes
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 ...
• 18.7k
3 votes
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 ...
• 14.8k
3 votes

### 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 ...
3 votes
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....
• 1,516
2 votes

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

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 \{...
• 1,733
2 votes
Accepted

### Question on deduction that a certain problem requires exponential space

Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard Space Hierarchy Theorem. The standard version of the Space Hierarchy Theorem has the ...
• 1,733

Only top scored, non community-wiki answers of a minimum length are eligible