75
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ making this CW, since it could be a long list. $\endgroup$
    – Suresh Venkat
    Commented Jan 23, 2011 at 1:31
  • 4
    $\begingroup$ Is there a metric for 'near-impossible-to-implement'? Is there theory that defines it? $\endgroup$
    – Ritwik Bose
    Commented Jan 23, 2011 at 21:52
  • $\begingroup$ @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. :) $\endgroup$
    – Radu GRIGore
    Commented Jan 24, 2011 at 8:38
  • $\begingroup$ @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 $\endgroup$
    – Ritwik Bose
    Commented Jan 24, 2011 at 10:12
  • 4
    $\begingroup$ 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? $\endgroup$
    – Simd
    Commented Jan 24, 2011 at 18:45

9 Answers 9

Reset to default
36
$\begingroup$

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"

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ Does the algorithm have reasonable constants? $\endgroup$
    – jbapple
    Commented Jan 25, 2011 at 8:01
  • $\begingroup$ Is this the only known linear time algorithm for the problem? $\endgroup$
    – Thomas Ahle
    Commented Nov 17, 2013 at 22:17
  • 2
    $\begingroup$ @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/… $\endgroup$
    – Sasho Nikolov
    Commented Feb 20, 2014 at 21:41
  • 1
    $\begingroup$ 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 $\endgroup$
    – Ralph Boland
    Commented Oct 11, 2015 at 2:01
  • 1
    $\begingroup$ @user1271772: I don't believe anybody has made a serious effort to figure out whether there's a version of Chazelle's algorithm with reasonable constants. Since there are several very simple $O(n\log n)$ algorithms with small constants, the amount of computation time it would save is clearly dwarfed by the enormous cost of programming it up. You probably never want to triangulate any polygons with more than a few hundred edges, and for this size it's hard to imagine it could beat the $O(n \log n)$ algorithms. $\endgroup$
    – Peter Shor
    Commented Jul 24, 2018 at 22:11
32
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Wikipedia also points out that this is not an algorithm but a semi-algorithm because it requires heuristics for solving the constant problem. $\endgroup$
    – sclv
    Commented Jan 25, 2011 at 15:22
  • $\begingroup$ What is heuristics? Can you give some link to read more about it? $\endgroup$
    – zygimantus
    Commented Jan 5, 2016 at 17:31
24
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • 3
    $\begingroup$ Is this also hard to implement or just has a huge constant? $\endgroup$
    – Lev Reyzin ♦
    Commented Jan 23, 2011 at 23:52
  • 5
    $\begingroup$ 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 :-) $\endgroup$
    – Aryabhata
    Commented Jan 24, 2011 at 0:43
  • 5
    $\begingroup$ 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 . $\endgroup$
    – Suresh Venkat
    Commented Jan 24, 2011 at 5:08
  • 2
    $\begingroup$ For instance, we don't even know the list of excluded minors for graphs embeddable in the torus. $\endgroup$
    – Derrick Stolee
    Commented Jan 24, 2011 at 15:00
  • 19
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Jan 24, 2011 at 18:21
16
$\begingroup$

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.

Improve this answer
$\endgroup$
13
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Jake
    Commented Oct 11, 2015 at 3:46
11
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is unlikely to have practical value even if implemented, due to the large exponential (sic) dependence on genus. $\endgroup$
    – Jeffε
    Commented Jan 26, 2011 at 5:43
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Jan 27, 2011 at 14:45
3
$\begingroup$

Tree decomposition, and perhaps Fibonacci heaps.

Improve this answer
$\endgroup$
8
  • 17
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Jan 24, 2011 at 1:01
  • 1
    $\begingroup$ 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 $\endgroup$
    – Yaroslav Bulatov
    Commented Jan 24, 2011 at 2:53
  • 3
    $\begingroup$ 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 $\endgroup$
    – Yaroslav Bulatov
    Commented Jan 24, 2011 at 3:48
  • 4
    $\begingroup$ 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. $\endgroup$
    – Bart Jansen
    Commented Jun 10, 2011 at 8:52
  • 3
    $\begingroup$ I think this is the best implementation effort: hein.roehrig.name/dipl $\endgroup$
    – didest
    Commented Jun 15, 2011 at 20:21
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jul 24, 2018 at 21:02

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