New answers tagged time-complexity
0
In many cases you can tweak space/time trade-offs, but this highly depends on the exact model of computation.
As an example, in the "WORD RAM" model, you can sort in linear time using counting sort, but need space that may be (roughly speaking) exponential in N.
Note that "initializing" your space (to 0 for example) can be done in O(1) ...
2
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)...
0
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 ...
5
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 ...
0
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$-...
3
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 ...
0
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: https://en.wikipedia.org/wiki/Game_complexity
The notion of "memory-hard functions" was developed as functions that are precisely designed to require large space to ...
1
Yes, let's require even less and say you're just interested in figuring out if the difference (similarly, intersection) is empty or not. It is trivial to have a quadratic-sized data structure with constant time query (by pre-processing everything) and also a linear-sized structure with linear query time (by just storing the sets trivially), and it's natural ...
4
(Sorry but not enough reputation otherwise this would be a comment.)
Note that set difference is equivalent to set intersection with the complement i.e. $S_i\backslash S_j = S_i \cap \overline{S_j}$. Thus you could double the number of sets to $S_1, S_2, ...., S_k, \overline{S_1}, ..., \overline{S_k}$ and apply the set intersection pre-processing to the ...
Top 50 recent answers are included
