# 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. Aug 4 '14 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 Aug 4 '14 at 19:06

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
Aug 4 '14 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. Aug 12 '14 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. Aug 12 '14 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). Aug 12 '14 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.