Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? It puts a hard upper bound on what you can do, whereas time is only a factor if you're 'impatient.'
Preferably something practical.
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 some computations can reasonably be done in practice (e.g. using Macaulay2 or SINGULAR), but very often it quickly eats up all the space and crashes. I think one of the first papers to look at this was Bayer & Mumford "What can be computed in algebraic geometry?".
(FWIW, my recent experience with these programs has been that there is a trichotomy: either the answer returns in (1) seconds, (2) a few minutes, or (3) so long that you give up / so much memory that it crashes.)
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/Held%E2%80%93Karp_algorithm). It's not the choice in practice for this problem (instead, branch-and-cut methods like in CONCORDE are faster) but it has the best proven time guarantees for the general problem, and its $O(n^2 2^n)$ time and $O(n2^n)$ space are in the range to make the space bound the bottleneck. There are alternative algorithms using polynomial space but with a higher exponential time bound, roughly $4^n$.
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" the set of satisfying assignments to a CNF formula $\psi$ into a Binary Decision Diagram (a kind of directed acyclic labelled graph). Once this is (expensive) computation is done, one can then do many things cheaply that are usually expensive.
For example, one can count the satisfying assignments of a CNF formula in time linear in the size of this BDD graph. If you have compiled two CNFs $\phi,\psi$ into BDDs, then you can check whether $\phi\implies \psi$, and count $|\phi\wedge \psi|$, in time $\Theta(|\phi|_{\text{BDD}}\cdot |\psi|_{\text{BDD}})$. This is significant, because a BDD can be exponentially smaller than the set that it encodes: some formulas have an exponential number of satisfying assignments, but have a BDD of size only, say, $\mathcal{O}(n^2)$. The BDD of any clause $(x_1\vee x_2\vee\cdots\vee x_{k})$ has size only $\Theta(k)$, so after building the BDD of a formula $\phi$ BDD once, one can then check for clausal entailment $\phi\implies (x_1\vee x_2\vee\cdots\vee x_k)$, for any clause, very quickly, in time $\Theta(|\psi|_{\text{BDD}}\cdot k)$. Normally these computations are $\#\text{P}$-Complete and $\text{NP}$-Complete, respectively.
In an ideal situation, we have the opportunity to build the BDD during "preprocessing time", and once we're done, we hear which query we are supposed to answer. Then the limiting factor is that the BDD may grow exponentially in size. This blowup was always unavoidable, of course: We are trying to do intractable computations in polynomial time, so the tradeoff that we make is that the representation is exponentially large. Fortunately, in practice, this exponential behaviour rarely happens, and many interesting functions and systems can be represented by surprisingly small BDDs. For example, formulas with small treewidth have small BDDs.
Another wonderful application: the set $A$ is be the set of reachable configurations of a piece of software, or the reachable positions in chess. This is how BDDs made their debut: One can do exhaustive search on the state space of a program by compiling it into a BDD, and then one checks, for example, whether that set contains an element in which the program counters of two threads are in the same critical section. This last predicate is a simple formula with a small BDD, so intersection checking is fast.
Since the introduction of BDDs in 1986 [1], a large zoo of new diagrams have sprung up for this purpose: ZDDs, Tagged BDDs, SDDs, d-DNNFs. They make time/space tradeoffs: They are more compact, but support less queries. A good (but slightly out-of-date) overview is A knowledge compilation map [2]. All these diagrams are ultimately Boolean circuits, so finding out which ones are more compact than others is a difficult question of circuit lower bounds, so is part of computational complexity theory.
Of course BDDs are not always the answer, and modern model checking seems to favour SAT-based approaches, but Bryant's paper has 12k citations, so it is safe to say that people have found some uses for them.
[1] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.
[2] Darwiche, Adnan, and Pierre Marquis. "A knowledge compilation map." Journal of Artificial Intelligence Research 17 (2002): 229-264.
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, which has both time and space complexity $\mathcal O(nm)$.
When applied to mammalian whole-genome alignments, this would naïvely require in the order of exabytes of space. Even bacterial genome alignments still require terabytes. By contrast, there’s a clever variation of the algorithm due to Hirshberg that uses divide & conquer to require only linear space ($\mathcal O(\min\{n,m\})$). This algorithm is also faster in practice (because it reduces the search space) but even if it didn’t improve the runtime it would still be practically feasible, whereas Needleman and Wunsch’s algorithm has prohibitive space requirements for all but small sequences.
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 practice --- approximating it to some polynomial approx factor is already sufficient to break cryptography), but algorithms solving the Shortest Vector Problem in $n$-dimensional integer lattices fall into a few different classes:
This is to say all known exact SVP algorithms with provable running time $2^{O(n)}$ use exponential space, and algorithms with polynomial space usage have running time $2^{\omega(n)}$.
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 commodity and edge pair) and the number of constraints is roughly $m$. Now if you try to run the flow problem via simplex based algorithms then the incidence matrix is too large and inverting it creates a dense matrix which does not often fit in memory even though the initial problem is of reasonable size. This is one reason people use column generation and approximate iterative methods.
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. A historical example, in which many algorithms could be discussed to make the point, would be old-school video games. I won't go into much detail here, but will lean on links; for now, it suffices to say it's mostly been about reducing the redundancy in data, sometimes caring literally about every single bit.
Nowadays, you can afford to give every pixel independent 24-bit colour in every frame. But there was a time you couldn't even achieve 2-bit colour that way, due to limited RAM. The reason that's no longer true is because RAM has grown much more in the last 40 years or so than screen resolution has. There were similar issues with audio.
The same period has also seen hardware expand how large the whole game can be, which may not sound like an algorithm detail, but it is because (1) game developers used to have to do all sorts of inventive things to do all they could with memory (here's a modern take on just a few of them) and (2) modern games' large size is typically used to cache a lot of data, thereby reducing time complexity (if only by a $O(1)$ factor).
The history of video games is roughly a transition from space complexity being the limiting factor to time complexity being the limiting factor, and there was a period when both were very important. For example, Andy Gavin had to be very innovative with both, but again a lot of it comes down to $O(1)$ factors.
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 a time complexity of O(1) but the space complexity will be based upon the number of possible inputs. You can think of this as an analog to the old days where mathematics textbooks had charts for things like logarithms or sine/cosine etc.
I have practically used these algorithms in embedded systems where the range of inputs was limited the range of a couple of 8-bit unsigned integers. I have also seen production code that had a look up table for a range of sine values of limited input precision.
This use case does not come up very often as input ranges are not commonly nicely range constrained or an output can depend on many variable or even worse if the order of the inputs matters (think traveling salesman)
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, just about any computational process can be drastically optimized with memoization (lookup tables), inlining, and unrolling. I would say just about all efficient algorithms ultimately boil down to the application of memoization at various points in the computational process. Inserting data into a lookup table is like pre-computing specific aspects of the problem. In the extreme case, you can completely cache any function to achieve $O(1)$ complexity, provided you're happy to precompute every possible input and use a lookup table of size $2^{\#input\ bits}$.
We don't talk about compiler optimizations like inlining and unrolling very much in practice, but they are equally important for efficient computation. The compiler often ends up inflating the executable size in order to eliminate redundant conditional checks.
You could also view data compression as being a trade-off between time and space complexity. Totally uncompressed data can be loaded linearly with respect to its size. Compressed data takes at least that long since it had to load the final data into memory and account for any computational overhead associated with compression and decompression.
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.
I remembering hearing that early suffix tree algorithms suffered from space constraints:
Linear time, exponential space: Linear Pattern Matching Algorithms (1973)
Linear time, quadratic space: A Space-Economical Suffix Tree Construction Algorithm (1976)
The space (obviously) isn't fully written to, but must be allocated in their models of computation to ensure the time complexities they're trying to achieve.
Unfortunately, these examples are the only info I have from old notes I have lying around, and I'm not currently clear on which precise part of each paper each one refers to. Hopefully they're correct, but if someone has more info, please help me update this answer.
There are at least a few areas in practice I can think of:
Lots of games are PSPACE-hard, meaning you'll necessarily need a lot of space to play them optimally. See a table here: Wikipedia – Game complexity
The notion of "memory-hard functions" was developed as functions that are precisely designed to require large space to compute so that "technological shortcuts" can't allow an adversary to compute them more efficiently than expected, in other words, when hardness should translate to needing more real physical materials. They're of immense use in cryptography, especially for proof of work primitives in cryptocurrency. See Wikipedia – Memory hard function.
In machine learning, space can be a limiting factor. Among the provable results, the recent work by Ran Raz stands out.
