Powerful Algorithms too complex to implement

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.

-
making this CW, since it could be a long list. –  Suresh Venkat Jan 23 '11 at 1:31
Is there a metric for 'near-impossible-to-implement'? Is there theory that defines it? –  mechko 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 –  mechko Jan 24 '11 at 10:12
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"

-
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
@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

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

-
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

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".

-
Is this also hard to implement or just has a huge constant? –  Lev Reyzin Jan 23 '11 at 23:52
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
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
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
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.

-

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)

-
This is unlikely to have practical value even if implemented, due to the large exponential (sic) dependence on genus. –  JɛﬀE Jan 26 '11 at 5:43

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

-

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.".

-
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. –  JɛﬀE Jan 27 '11 at 14:45
+1: thanks, and sorry about the goof, I'll update my answer accordingly. –  Anthony Labarre Jan 27 '11 at 15:53

Tree decomposition, and perhaps Fibonacci heaps.

-
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
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
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
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
I think this is the best implementation effort: hein.roehrig.name/dipl –  Diego de Estrada Jun 15 '11 at 20:21