13
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think you might find what you seek in the parameterized complexity literature. $\endgroup$
    – Kaveh
    Commented Aug 4, 2014 at 16:28
  • $\begingroup$ 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 $\endgroup$
    – Grady Player
    Commented Aug 4, 2014 at 19:06

3 Answers 3

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ @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". $\endgroup$
    – R B
    Commented Aug 4, 2014 at 10:51
12
$\begingroup$

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.

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

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:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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