<p>Modern <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT">SAT solving algorithms</a> are able to solve most instances quite fast, even though the worst case running time is, of course, exponential. In this case, however, the practical speed is more of a result of years of algorithm engineering, rather than that of a single elegant algorithm. While I've understood that conflict driven clause learning caused a major jump in the performance of SAT solvers, the later improvements are have often been achieved by a clever use of various heuristics in the algorithms.</p>

CC BY-SA 4.0
2020-07-22T05:16:06.380Z
The other factor is that people generally only use them on problems which are amenable to CDCL based solving. It is very easy to run into problems where SAT solvers don't work, but people don't use SAT solvers on those problems for obvious reasons.
Antimony
CC BY-SA 2.5
2010-11-18T07:45:53.650Z
2010-11-18T07:45:53.650Z
Janne H. Korhonen
<p>Hindley-Milner type inference is EXPTIME-complete, but on the programs people typically write it is pretty close to linear. </p>

CC BY-SA 3.0
2016-04-20T20:36:45.487Z
The example is in SML, and I am more familiar with OCaml's way of doing things, but if that sequence of bindings were "let"s, then I think they *would* be nested. It is only because they define global functions that they are not, but there is an implicit nesting going on here: A given definition has access to all the definitions above it and none of those below.
amnn
CC BY-SA 3.0
2016-04-21T09:58:40.937Z
@amnn: The nesting referred to was nesting lets in the form being bound -- i.e., `let z = (let y = e in e') in e''` as opposed to than  `let y = e in let z = e' in e''`.
Neel Krishnaswami
CC BY-SA 2.5
2010-11-18T16:10:17.783Z
Isn't this a bit different though? My recollection is that we could characterize a necessary condition for Hindley-Milner performing badly (deeply nested lets) and so the reason HM is good in practice is that this nesting is, in practice, bounded pretty low (usually we indent more as we go deeper into let bindings and get nervous as we head towards the rightmost edge of the screen...) Granted, I have made this claim from memory before and I was most recently unable to recover the reference for it.
Rob Simmons
CC BY-SA 2.5
2010-11-18T17:52:50.767Z
No, that's not a necessary condition. You can give a sequence of let-bindings (with no nesting!) such that it squares the size of the inferred type with each additional entry in the sequence.  See http://cstheory.stackexchange.com/questions/2428/context-sensitive-grammars-and-types/2439#2439 for an example.
Neel Krishnaswami
CC BY-SA 2.5
2010-11-18T08:50:06.160Z
2010-11-18T08:50:06.160Z
Neel Krishnaswami
<p>The $k$-means algorithm for clustering is provably exponential even in the plane, but it works very well in practice. </p>

CC BY-SA 2.5
2010-11-18T07:47:09.917Z
2010-11-18T07:47:09.917Z
Suresh Venkat
<p>Brendan McKay's <a href="http://cs.anu.edu.au/~bdm/nauty/" rel="noreferrer">nauty</a> (No AUTomorphisms, Yes?) program solves the canonical labeling problem of graphs (simultaneously solving the Graph Isomorphism and Graph Automorphism problems) and has <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.3532" rel="noreferrer">exponential worst-case performance</a> (Miyazaki, 1996).  However, it works very quickly for most graphs, especially those with a few automorphisms.</p>

<p>Specifically, the algorithm begins by partitioning the vertices by degree, then by the degree between each part.  When this process stabilizes, a choice must be made to distinguish a vertex in a non-trivial part, and this leads to the exponential behavior.  In most graphs, the depth of this branching procedure is small.</p>

CC BY-SA 2.5
2010-11-18T16:52:39.500Z
I thought that nauty also used some randomness to help in refinement? In that case, this might be very analogous to the simplex algorithm (although there's not obviously a notion of smoothed analysis for graph isomorphism).
Joshua Grochow
CC BY-SA 2.5
2010-11-18T17:08:26.563Z
It doesn't use randomness, since it needs to make a consistent canonical labeling.  However, it can use a custom-built vertex-invariant procedure in order to help partition the vertices.  Sometimes this invariant looks random how it was produced (frequently, it's a complicated function on distance-degree sequences), but that's just to reduce collisions.
Derrick Stolee
CC BY-SA 2.5
2010-11-18T17:09:03.897Z
This vertex-invariant can be compared to the anti-cycling rules of the simplex algorithm.
Derrick Stolee
CC BY-SA 2.5
2010-11-18T15:22:12.500Z
2010-11-18T15:30:32.443Z
2010-11-18T15:30:32.443Z
Derrick Stolee
<p>Several <a href="http://scholar.google.com/scholar?cluster=11993743079293931240&amp;hl=en&amp;as_sdt=40000000" rel="nofollow">algorithms for simple stochastic games</a> work well in practice, even though they have exponential worst-case running times. Of course, this problem is in some sense related to linear programming, although it is not known to be in polynomial time.</p>

CC BY-SA 4.0
2024-08-13T15:27:32.037Z
broken link can't find in archieve either: https://web.archive.org/web/20210201000000*/http://scholar.google.com/scholar?cluster=11993743079293931240&hl=en&as_sdt=40000000
SiminSimin
CC BY-SA 2.5
2010-11-18T19:33:18.510Z
2010-11-18T19:53:05.083Z
2010-11-18T19:53:05.083Z
Peter Shor 
<p>There's an algorithm for finding mixed Nash equilibria that's similar to the simplex algorithm for LPs. (I forget the name.) It has exponential worst-case complexity, but I have a vague memory that it often behaves well in practice.</p>

CC BY-SA 2.5
2011-02-02T20:57:45.340Z
Do you mean the Lemke-Howson algorithm?
Rahul Savani
CC BY-SA 2.5
2010-11-18T17:15:04.383Z
2010-11-18T17:15:04.383Z
Warren Schudy
<p>Bin packing (many variants) is a problem whose complexity is known to be NP-hard:</p>

<p><a href="http://en.wikipedia.org/wiki/Bin_packing_problem" rel="nofollow">http://en.wikipedia.org/wiki/Bin_packing_problem</a></p>

<p>However, many heuristics when applied to "practical" versions do very well. For 1-dimensional bin packing some of these heuristics, like first-fit; first-fit decreasing; best-fit; best-fit decreasing are very appealing as topics to show students. Students often can discover some of the basic heuristics for themselves.</p>

CC BY-SA 2.5
2010-11-18T22:43:07.367Z
There are many examples evenif the problem is NP-complete, simple algortihms can deal with it.Especially with approximation algorithms. But I am actually looking for exponential-time algorithms, your example is related to a hard problem which is easy to solve with simple algorithms. 

Maybe there is an exponential time algorithm to solve Bin packing (or another problem) exactly; and in practice it takes polynomial time.
Arman
CC BY-SA 2.5
2010-11-18T18:58:42.443Z
2010-11-18T18:58:42.443Z
Joseph Malkevitch
<p>We generally call an algorithm "good algorithm" if it's runnning time is polynomial in the worst-case.
But in some cases (for example Simplex algorithm), eventhough the worst-case of the algorithm is exponential, it could work very well in practice. </p>

<p>Are there any (deterministic) examples to this situatation other than Simplex algorithm? </p>

CC BY-SA 2.5
2010-11-18T19:10:47.753Z
You may be interested in a related question: http://cstheory.stackexchange.com/questions/305/for-which-algorithms-is-there-a-large-gap-between-the-theoretical-analysis-and-re
Radu GRIGore
<ds.algorithms>
Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?
Arman
# Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?

(Asked by: username_0 on 2010-11-18)

We generally call an algorithm "good algorithm" if it's runnning time is polynomial in the worst-case.
But in some cases (for example Simplex algorithm), eventhough the worst-case of the algorithm is exponential, it could work very well in practice.

Are there any (deterministic) examples to this situatation other than Simplex algorithm?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: You may be interested in a related question: http://cstheory.stackexchange.com/questions/305/for-which-algorithms-is-there-a-large-gap-between-the-theoretical-analysis-and-re  

---

## 7 answers

### Answer by username_7 on 2010-11-18. Score: 15

The $k$-means algorithm for clustering is provably exponential even in the plane, but it works very well in practice.


---

### Answer by username_2 on 2010-11-18. Score: 14

Modern [SAT solving algorithms](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT) are able to solve most instances quite fast, even though the worst case running time is, of course, exponential. In this case, however, the practical speed is more of a result of years of algorithm engineering, rather than that of a single elegant algorithm. While I've understood that conflict driven clause learning caused a major jump in the performance of SAT solvers, the later improvements are have often been achieved by a clever use of various heuristics in the algorithms.

> **Comments:**
> **username_3**: The other factor is that people generally only use them on problems which are amenable to CDCL based solving. It is very easy to run into problems where SAT solvers don't work, but people don't use SAT solvers on those problems for obvious reasons.  

---

### Answer by username_4 on 2010-11-18. Score: 13

Hindley-Milner type inference is EXPTIME-complete, but on the programs people typically write it is pretty close to linear.

> **Comments:**
> **username_6**: Isn't this a bit different though? My recollection is that we could characterize a necessary condition for Hindley-Milner performing badly (deeply nested lets) and so the reason HM is good in practice is that this nesting is, in practice, bounded pretty low (usually we indent more as we go deeper into let bindings and get nervous as we head towards the rightmost edge of the screen...) Granted, I have made this claim from memory before and I was most recently unable to recover the reference for it.  
> **username_4**: No, that's not a necessary condition. You can give a sequence of let-bindings (with no nesting!) such that it squares the size of the inferred type with each additional entry in the sequence.  See http://cstheory.stackexchange.com/questions/2428/context-sensitive-grammars-and-types/2439#2439 for an example.  
> **username_5**: The example is in SML, and I am more familiar with OCaml's way of doing things, but if that sequence of bindings were "let"s, then I think they *would* be nested. It is only because they define global functions that they are not, but there is an implicit nesting going on here: A given definition has access to all the definitions above it and none of those below.  
> **username_4**: @username_5: The nesting referred to was nesting lets in the form being bound -- i.e., `let z = (let y = e in e') in e''` as opposed to than  `let y = e in let z = e' in e''`.  

---

### Answer by username_8 on 2010-11-18. Score: 10

Brendan McKay's [nauty](http://cs.anu.edu.au/~bdm/nauty/) (No AUTomorphisms, Yes?) program solves the canonical labeling problem of graphs (simultaneously solving the Graph Isomorphism and Graph Automorphism problems) and has [exponential worst-case performance](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.3532) (Miyazaki, 1996). However, it works very quickly for most graphs, especially those with a few automorphisms.

Specifically, the algorithm begins by partitioning the vertices by degree, then by the degree between each part. When this process stabilizes, a choice must be made to distinguish a vertex in a non-trivial part, and this leads to the exponential behavior. In most graphs, the depth of this branching procedure is small.

> **Comments:**
> **username_9**: I thought that nauty also used some randomness to help in refinement? In that case, this might be very analogous to the simplex algorithm (although there's not obviously a notion of smoothed analysis for graph isomorphism).  
> **username_8**: It doesn't use randomness, since it needs to make a consistent canonical labeling.  However, it can use a custom-built vertex-invariant procedure in order to help partition the vertices.  Sometimes this invariant looks random how it was produced (frequently, it's a complicated function on distance-degree sequences), but that's just to reduce collisions.  
> **username_8**: This vertex-invariant can be compared to the anti-cycling rules of the simplex algorithm.  

---

### Answer by username_10 on 2010-11-18. Score: 5

Several [algorithms for simple stochastic games](http://scholar.google.com/scholar?cluster=11993743079293931240&hl=en&as_sdt=40000000) work well in practice, even though they have exponential worst-case running times. Of course, this problem is in some sense related to linear programming, although it is not known to be in polynomial time.

> **Comments:**
> **username_11**: broken link can't find in archieve either: https://web.archive.org/web/20210201000000*/http://scholar.google.com/scholar?cluster=11993743079293931240&hl=en&as_sdt=40000000  

---

### Answer by username_12 on 2010-11-18. Score: 2

There's an algorithm for finding mixed Nash equilibria that's similar to the simplex algorithm for LPs. (I forget the name.) It has exponential worst-case complexity, but I have a vague memory that it often behaves well in practice.

> **Comments:**
> **username_13**: Do you mean the Lemke-Howson algorithm?  

---

### Answer by username_14 on 2010-11-18. Score: 1

Bin packing (many variants) is a problem whose complexity is known to be NP-hard:

<http://en.wikipedia.org/wiki/Bin_packing_problem>

However, many heuristics when applied to "practical" versions do very well. For 1-dimensional bin packing some of these heuristics, like first-fit; first-fit decreasing; best-fit; best-fit decreasing are very appealing as topics to show students. Students often can discover some of the basic heuristics for themselves.

> **Comments:**
> **username_0**: There are many examples evenif the problem is NP-complete, simple algortihms can deal with it.Especially with approximation algorithms. But I am actually looking for exponential-time algorithms, your example is related to a hard problem which is easy to solve with simple algorithms.   Maybe there is an exponential time algorithm to solve Bin packing (or another problem) exactly; and in practice it takes polynomial time.  

---

