What are some algorithms of legitimate utility that are simply too complex to implement?

Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm (Coppersmith-Winograd), which is reasonable to implement but has a constant that makes it useless in practice. I'm looking for algorithms that could plausibly have practical value, but are so difficult to code that they have never been implemented, only implemented in extremely artificial settings, or only implemented for remarkably special-purpose applications.

Also welcome are near-impossible-to-implement algorithms that have good asymptotics but would likely have poor real performance.

  • 1
    making this CW, since it could be a long list. – Suresh Venkat Jan 23 '11 at 1:31
  • 4
    Is there a metric for 'near-impossible-to-implement'? Is there theory that defines it? – Ritwik Bose Jan 23 '11 at 21:52
  • @Mechko, perhaps a lower bound on the size of the smallest Turing machine that outputs a description of a Turing machine that is an implementation of the algorithm. :) – Radu GRIGore Jan 24 '11 at 8:38
  • @Radu GRIGore is this an accepted metric or one that ought to be developed? I suppose that (for now) there is a simple, immovable line that defines 'meh, not worth it'... :D – Ritwik Bose Jan 24 '11 at 10:12
  • 4
    I am interested by the suggestion that Coppersmith-Winograd is reasonable to implement. Has anyone ever seen an implementation written down even in high level pseudo-code and has anyone ever estimated the constants? – Raphael Jan 24 '11 at 18:45

Chazelle gave a linear time algorithm for triangulating a simple polygon. Skiena wrote (p.575, Algorithm Design Manual) that it's "sufficiently hopeless to implement that it qualifies more as an existence proof"

  • 3
    Does the algorithm have reasonable constants? – jbapple Jan 25 '11 at 8:01
  • Is this the only known linear time algorithm for the problem? – Thomas Ahle Nov 17 '13 at 22:17
  • 2
    @ThomasAhle I believe it is the only known deterministic linear time algorithm. Amato, Goodrich, and Ramos have a simpler randomized one: cs.princeton.edu/courses/archive/fall05/cos528/handouts/… – Sasho Nikolov Feb 20 '14 at 21:41
  • Chazelle's linear time simple polygon triangulation algorithm, to my knowledge, has never been implemented and likely never will be because of it's complexity and also because constants are high so it won't be able to compete with alternatives in practice. Major theoretical achievement though. Ralph Boland – Ralph Boland Oct 11 '15 at 2:01
  • I'll ask again: Does the algorithm have reasonable constants? – user1271772 May 2 '17 at 20:03

The Risch algorithm for computing elementary antiderivatives. According to Wikipedia, no software package is known to implement the full algorithm due to its complexity.

  • 3
    Wikipedia also points out that this is not an algorithm but a semi-algorithm because it requires heuristics for solving the constant problem. – sclv Jan 25 '11 at 15:22
  • What is heuristics? Can you give some link to read more about it? – zygimantus Jan 5 '16 at 17:31

Any algorithm that uses the Robertson-Seymour results to infer a "polytime" algorithm for things involving graphs that exclude a fixed minor is asking for trouble. The constant hidden in their result is "galactic".

  • 3
    Is this also hard to implement or just has a huge constant? – Lev Reyzin Jan 23 '11 at 23:52
  • 5
    Yes, this does not look like a good example. If I understand correctly, the question is about algorithms which could be practical (hence likely 'small' constants) but are just too complex to implement. Of course, the whole question is open to different interpretations :-) – Aryabhata Jan 24 '11 at 0:43
  • 5
    The problem is the constant comes from the very large list of minors that one needs to exclude for a particular property. I don't know of any way to generate the desired list of excluded minors for a given property, so it's not just a scale issue . – Suresh Venkat Jan 24 '11 at 5:08
  • 2
    For instance, we don't even know the list of excluded minors for graphs embeddable in the torus. – Derrick Stolee Jan 24 '11 at 15:00
  • 15
    The problem here seems deeper: there is no effective way known to generate the list of minors, so this doesn't actually yield an algorithm at all. Most minor-closed properties yield an infinite list of excluded minors, if one translates the logical expression directly. The Robertson-Seymour Theorem (Wagner's Conjecture) tells us that a finite list of excluded minors is lurking inside that infinite list, but the theorem gives absolutely no help in actually finding them. So Robertson-Seymour therefore usually leads to a pure existence proof. – András Salamon Jan 24 '11 at 18:21

Dan Willard's "A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time" describes an algorithm for maintaining an ordered set in an array of size $O(n)$ with insertion and deletion in $O(\frac{\log^2 n}{B})$ worst-case time, where $B$ is the page size.

The paper is 55 pages long, and its conclusion notes several improvements to the constants that the author does not describe for reasons of space. This makes me suspect that perhaps the constants aren't so galactic, and that this data structure would be of "legitimate utility", especially since it has been cited many times.

The linear time higher-order pattern unification algorithm by Qian has never been implemented due to its complexity AFAIK.

  • Luckily there are practical algorithms for it still. The handbook of automated reasoning says it can be done in polytime (right beside where it cites Qian's algorithm) so that's pretty awesome. – Jake Oct 11 '15 at 3:46

Linear-time algorithm to check if a graph can be embedded in a fixed surface.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. FOCS 2008: 771-780.

Bojan Mohar: A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface. SIAM J. Discrete Math. 12(1): 6-26 (1999)

  • 1
    This is unlikely to have practical value even if implemented, due to the large exponential (sic) dependence on genus. – Jeffε Jan 26 '11 at 5:43

I'm not sure how useful it could be in practice (although I'm thinking about protein folding and comparison, as well as RNA secondary structure prediction), but Wolfgang Haken gave the first polynomial-time algorithm for deciding whether a knot is a simple loop (Theorie der Normalflächen. Acta Math. 105, 1961, pp. 245--375). As I recall, it is still too complicated to be implemented all those decades later.

If Wikipedia is to be believed, several other algorithms were later given, and "Understanding the complexity of these algorithms is an active field of study.".

  • 4
    Haken gave the first algorithm, but it does not run in polynomial time; in fact, no poly-time algorithm (or NP-hardness result) is known. More recent work has reduced knot triviality (via Haken's normal-surface formulation) to integer programming, which is usually quick to solve in practice. – Jeffε Jan 27 '11 at 14:45

Tree decomposition, and perhaps Fibonacci heaps.

  • 14
    Fibonacci heaps are certainly not too complicated to implement; they have been implemented, and tested. The problem with them is rather that their practical performance is not as good as some other heaps due to largish constant factors in their running time. – David Eppstein Jan 24 '11 at 1:01
  • 1
    I wrote a package to find tree decomposition, and I don't think it's hard to implement yaroslavvb.blogspot.com/2011/01/building-junction-trees.html – Yaroslav Bulatov Jan 24 '11 at 2:53
  • 2
    My code is just a heuristic tree-decomposition, not optimal like branch-and-bound and dynamic programming approaches...I'm guessing you meant Bodlaender's "A Linear Time Algorithm ..."? I have not seen any implementations of that – Yaroslav Bulatov Jan 24 '11 at 3:48
  • 4
    Bodlaender's linear-time algorithm uses a dynamic-programming algorithm from an earlier paper as a subroutine: that algorithm computes an optimal treedecomposition in something like $2^{O(k^3)} O(n)$ time, when given an approximate-treedecomposition of width k as input. I think I recall that Hans Bodlaender once told me that they implemented this dynamic programming algorithm that is used as a subroutine, but it was already too slow for k=3. The dynamic programming is the main part of the linear-time algorithm, so Bodlaender's algorithm is not too hard to implement, just too slow. – Bart Jansen Jun 10 '11 at 8:52
  • 3
    I think this is the best implementation effort: hein.roehrig.name/dipl – Diego de Estrada Jun 15 '11 at 20:21

Perfect hash construction (https://en.wikipedia.org/wiki/Perfect_hash_function#Construction) would apply to any use-case with static or infrequently-changing keys (e.g. top level domain names on routers, keywords in compilers, or function names in standard libraries) but the last time I looked I couldn't find any implementations.

Parametric search can solve many difficult optimization problems, including some that might look like they should be NP-hard, in polynomial time. The well-named paper Parametric search made practical implements a variant of parametric search, but still I do not think it has been implemented in practical software.

The optimal algorithm for line segment intersection by Chazelle and Edelsbrunner finds all $k$ intersections of $n$ line segments in $O(n \log n + k)$ time, but is complex. CGAL is a sophisticated geometry algorithm library, but implements a simpler algorithm that is $O((n+k) \log n)$.

  • 1
    I refuse to believe that the FKS construction is too complex to implement. It's actually quite straightforward. Maybe not practical, but certainly not too complex to implement. – Sasho Nikolov Jul 24 at 21:02

protected by Lev Reyzin Oct 12 '15 at 14:26

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.