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 ...
Jeffrey Shallit's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
William Hoza's user avatar
  • 1,733
11 votes
Accepted

Is $PSPACE$ believed to be different than $PP$?

I hope someone with more knowledge can supply an additional answer. I don't have a reference or a survey*, but in my experience people expect that $\text{PP}\subsetneq \text{PSPACE}$, mostly because, ...
Lieuwe Vinkhuijzen's user avatar
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 ...
Mateus de Oliveira Oliveira's user avatar
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 ...
daniello's user avatar
  • 3,256
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{...
Mikhail Rudoy's user avatar
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/...
David Eppstein's user avatar
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&...
Lieuwe Vinkhuijzen's user avatar
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, ...
Konrad Rudolph's user avatar
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 ...
William Hoza's user avatar
  • 1,733
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 ...
Lance Fortnow's user avatar
6 votes
Accepted

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

Define the language $BACKPOINTER$ to have words of length $n+t\log n$, divided to $1+t$ parts, one of length $n$ and the rest of length $\log n$, by commas such that $BACKPOINTER=\{(x,p_1,\ldots,p_t)\...
domotorp's user avatar
  • 14k
5 votes

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

One example is multicommodity flow problems via Simplex method. In these problems we have a graph $G=(V,E)$ with $n$ nodes and $m$ edges and $K$ commodities. The number of variables is $Km$ (one per ...
Chandra Chekuri's user avatar
5 votes

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

I don't know if the space complexity of this problem is limiting in practice (I have not personally run experiments to verify this, moreover I don't know anyone who needs to solve exact SVP in ...
Mark's user avatar
  • 918
5 votes
Accepted

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

No, this is impossible for your parameters. With $s$ bits of space, you can only visit at most $2^s$ vertices of the graph. Now set $s = O((\log k)^d)$ and $k=(\log n)^2$ and it is clear that you ...
D.W.'s user avatar
  • 11.6k
4 votes
Accepted

Space requirements for solving True Quantified Boolean Formulas problem

The main difference between time and space is that you can reuse space that is not needed anymore. If you return from the recursive call that evaluates $A$, you can reuse the space used by this ...
Daniel Borchmann's user avatar
4 votes

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

With this question we actually have to worry about $O(1)$ factors, because as you point out time can't be little o of space, but it can be much less demanding as a fraction of our hardware's abilities....
J.G.'s user avatar
  • 141
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 ...
CaptianObvious's user avatar
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....
Avi Tal's user avatar
  • 1,596
3 votes
Accepted

Is sliding blocks linear space complete?

Yes, sliding blocks, Rush Hour, and many other puzzles with reversible moves are (deterministic) linear space complete. By contrast, many puzzles with irreversible moves, including Sokoban, are ...
Dmytro Taranovsky's user avatar
3 votes

Complexity status of restricted k-clique

Yes. It is essentially same as the Clique problem. Imagine a clique containing $n$ nodes. Your problem is then asking for a Clique containing $n-1$ nodes, such that all of them are adjacent to vertex $...
TheoryQuest1's user avatar
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 ...
Emil Jeřábek's user avatar
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 \{...
William Hoza's user avatar
  • 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 ...
William Hoza's user avatar
  • 1,733
2 votes

Problem in the paper "Stable Minimum Space Partitioning in Linear Time"

There is no problem here. The paper (which I was led to by your question) could have been worded better, but the $O(\log n / \log \log n)$ counters use $O(\log \log n)$ bits each as they are used to ...
Dmytro Taranovsky's user avatar
1 vote

Bipartite graph projections, with threshold

My two cents: The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$. Maybe you are not looking for a worst case ...
maxdan94's user avatar
  • 563
1 vote

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

I think most non-trivial quantum algorithms fit the bill here as the space requirement to store complex amplitudes for an $n$ qubit system is $2^n$ in the general case.
Attila Kun's user avatar
1 vote

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

You may like to read about the space-time tradeoff. Generally speaking, it's a continuum of how far you're willing to go to strike a balance between space and efficiency. From a practical perspective, ...
user1318416's user avatar

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