# Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart.

For example, suppose a problem has a practical size* of $n = 100$ and there are two known algorithms: One is $2^n$ and the other is $n^c$ for some constant $c$. Clearly for any $c > 15$, the exponential algorithm is preferred.

*I guess practical size would mean something commonly found in the real world. Like the number of trains on a network.

• I think you might find what you seek in the parameterized complexity literature. Commented Aug 4, 2014 at 16:28
• for linear algorithms there is generally a constant multiplier that is generally not significant and often omitted from complexity, but one that I remember seeming very high was an in-place merge that was linear, but worst case something like 5000 N... so in those scenario's there is a large usable area where N^2 would be less than 5000 N where the size is less than sqrt(5000) and a smaller domain where 2^n would still be faster where n is less than log 5000 Commented Aug 4, 2014 at 19:06

## 3 Answers

How bout the simplex algorithm for linear programming? In many occasions it is used in practice.

Edited to add: I think it's more of a "worse-case exponential algorithm" which runs efficiently on practical instances/distributions rather than runs faster on practical sized adversarial instances.

• @diesalbla - it depends on the exact forumaltion. Citing Wikipedia, "in 1972, Klee and Minty[32] gave an example showing that the worst-case complexity of simplex method as formulated by Dantzig is exponential time".
– R B
Commented Aug 4, 2014 at 10:51

The fastest algorithm known for the problem of identifying whether a graph has a knotless embedding is due to Miller and Naimi, and is exponential-time. Robertson-Seymour theory says that there is an $O(n^3)$ algorithm for this problem; however, to write it down we would need to know the list of forbidden minors for knotless embeddings. However, even if we knew this list, the exponential-time algorithm would still be much faster for reasonable-size graphs, as there are over 250 forbidden minors, some of them quite large.

• Actually number of forbidden minors is not a big factor (even if there were 250 millions) but the part that says it takes time around(I'm not sure if it is exact): $2^{2^{2^{2^{|H|}}}}\cdot O(n^3)$, where $H$ is one of the forbidden minors is bad. It is actually impossible in practice even for |H|=2. Commented Aug 12, 2014 at 12:48
• It’s even $O(n^2)$ by sciencedirect.com/science/article/pii/S0095895611000712 , though I gather the dependence on $|H|$ is still horrible. Commented Aug 12, 2014 at 13:02
• Since deciding whether $H$ is a minor of $G$ is an NP-complete problem, one would think the dependence on $|H|$ has to be at least exponential (although note that Robertson-Seymour is quite a bit worse). Commented Aug 12, 2014 at 19:31

There are some examples with (nonprobabilistic/ exact) primality detection/ testing. The AKS algorithm was the first algorithm for primality testing shown to be in P. It does not compete favorably versus some exponential time algorithms for "small" inputs. The details are somewhat tricky because showing this generally requires actually implementing the algorithms which is a challenging exercise and can depend on implementation-specific aspects.

More info/details/refs on this cs.se question:

• As far as I am aware, the algorithms AKS competes with in practice are either randomized polynomial (Miller–Rabin, ECPP) or deterministic quasipolynomial (Adleman–Pomerance–Rumeley). Nowhere near exponential time. Commented Aug 4, 2014 at 15:40
• The randomized version of Miller–Rabin, which is the one used in practice, does not depend on RH. Commented Aug 4, 2014 at 15:56
• That’s all very true, but has nothing to do with the original question. Commented Aug 4, 2014 at 16:06
• Yes, I know all that. And for the third time, this is irrelevant. The question asks for exponential-time algorithms that are in practice competitive with a known polynomial-time algorithm (here, AKS). The only exponential-time primality testing algorithm used in practice is trial division, which is not competitive for numbers of any nontrivial size. The competitive algorithms used in practice are much more efficient than exponential, even though they are not polynomial (or deterministic, or unconditional). Commented Aug 4, 2014 at 16:17
• What is apples and oranges is comparing AKS (a primality testing algorithm) with GNFS (a factoring algorithm). Commented Aug 4, 2014 at 18:46