Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
I think you might find what you seek in the parameterized complexity literature. –  Kaveh Aug 4 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 –  Grady Player Aug 4 at 19:06

3 Answers 3

up vote 12 down vote accepted

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.

share|improve this answer
4  
@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 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.

share|improve this answer
5  
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. –  Saeed Aug 12 at 12:48
1  
It’s even $O(n^2)$ by sciencedirect.com/science/article/pii/S0095895611000712 , though I gather the dependence on $|H|$ is still horrible. –  Emil Jeřábek Aug 12 at 13:02
1  
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). –  Peter Shor Aug 12 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:

share|improve this answer
6  
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. –  Emil Jeřábek Aug 4 at 15:40
6  
The randomized version of Miller–Rabin, which is the one used in practice, does not depend on RH. –  Emil Jeřábek Aug 4 at 15:56
5  
That’s all very true, but has nothing to do with the original question. –  Emil Jeřábek Aug 4 at 16:06
2  
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). –  Emil Jeřábek Aug 4 at 16:17
3  
What is apples and oranges is comparing AKS (a primality testing algorithm) with GNFS (a factoring algorithm). –  Emil Jeřábek Aug 4 at 18:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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