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 ...
user avatar
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 ...
user avatar
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 ...
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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 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{...
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&...
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/...
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 ...
user avatar
  • 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, ...
user avatar
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 ...
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)\...
user avatar
  • 13.5k
5 votes

What is the space complexity of CTL model checking?

In general, CTL model checking is P-complete. Since we think that $L\neq P$ (and moreover $NL\neq P$), it is unlikely that an algorithm with logarithmic space exists. It is also unlikely that a sub-...
user avatar
  • 5,261
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 ...
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 ...
user avatar
  • 778
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 ...
user avatar
  • 10.5k
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 ...
user avatar
4 votes

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

First, I don't think the Arthur-Merlin protocol has to enter the model -- it sounds from the motivation like you just want to produce problem instances quickly so that any algorithm for solving them ...
user avatar
  • 7,090
4 votes

Does hyper-computational power of infinite time Turing machines also require infinite memory?

I think we have a reference here to Joel Hamkin's model of infinite time computation, not just some made up idea of infinite time machines. In that model time is measured by ordinal numbers. The ...
user avatar
  • 26.7k
4 votes
Accepted

Satisfiability for various branching programs

For Q2: For Ordered BDDs (OBDD) both satisfiability and counting solutions is polynomial in the size of the OBDD. For indexed BDD, IBDD p. 16 satisfiability is NP-complete and the equivalence test ...
user avatar
  • 1,955
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....
user avatar
  • 141
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 ...
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 $...
user avatar
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 ...
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 ...
user avatar
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 ...
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....
user avatar
  • 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 \{...
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 ...
user avatar
  • 1,733

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