<p>The <a href="http://arxiv.org/pdf/1109.1030v2.pdf">fastest algorithm known</a> 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 <a href="http://msp.org/agt/2014/14-03/agt-2014-14-059p.pdf">there are over 250 forbidden minors,</a> some of them quite large. </p>

CC BY-SA 3.0
2014-08-12T12:48:55.787Z
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
CC BY-SA 3.0
2014-08-12T13:02:07.037Z
It’s even $O(n^2)$ by http://www.sciencedirect.com/science/article/pii/S0095895611000712 , though I gather the dependence on $|H|$ is still horrible.
Emil Jeřábek
CC BY-SA 3.0
2014-08-12T19:31:43.227Z
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 
CC BY-SA 3.0
2014-08-11T17:07:34.897Z
2014-08-11T17:07:34.897Z
Peter Shor 
<p>There are some examples with (nonprobabilistic/ exact) <a href="http://en.wikipedia.org/wiki/Primality_test" rel="nofollow noreferrer">primality detection/ testing</a>. The <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow noreferrer">AKS algorithm</a> 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.</p>

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

<ul>
<li><a href="https://cs.stackexchange.com/questions/23260/when-is-the-aks-primality-test-actually-faster-than-other-tests">When is the AKS primality test actually faster than other tests?</a></li>
</ul>

CC BY-SA 3.0
2014-08-04T15:40:42.333Z
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
CC BY-SA 3.0
2014-08-04T15:54:29.663Z
Miller-Rabin depends on Riemann Hypothesis variations. etc. AKS first _unconditional_ P-time primality test.
vzn
CC BY-SA 3.0
2014-08-04T15:56:23.903Z
The randomized version of Miller–Rabin, which is the one used in practice, does not depend on RH.
Emil Jeřábek
CC BY-SA 3.0
2014-08-04T16:02:08.547Z
are you talking about a _probabilistic_ test? as wikipedia states re AKS: _AKS is the first primality-proving algorithm to be simultaneously general, polynomial, deterministic, and unconditional._ therefore other algorithms prior to AKS did not fit all those criteria simultaneously. eg those that were general, deterministic, and unconditional, were not _polynomial_.
vzn
CC BY-SA 3.0
2014-08-04T16:06:04.723Z
That’s all very true, but has nothing to do with the original question.
Emil Jeřábek
CC BY-SA 3.0
2014-08-04T16:08:58.680Z
??? eg one of your examples, re same wikipedia entry. "ECPP and APR conclusively prove or disprove that a given number is prime, but are not known to have polynomial time bounds for all inputs." also re your other example, randomized Miller Rabin, "Randomized tests, such as Miller–Rabin and Baillie–PSW, can test any given number for primality in polynomial time, but are known to produce only a probabilistic result."
vzn
CC BY-SA 3.0
2014-08-04T16:17:01.473Z
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
CC BY-SA 3.0
2014-08-04T16:22:31.037Z
doesnt the answer fit for a slightly less literal/ more broad interpretation of the question re "nonpolynomial" instead of "exponential"?
vzn
CC BY-SA 3.0
2014-08-04T16:30:27.133Z
That seriously changes the spirit of the question. There is nothing remarkable on the fact that a randomized polynomial-time algorithm can in practice run faster than a deterministic polynomial-time algorithm for the same problem.
Emil Jeřábek
CC BY-SA 3.0
2014-08-04T16:47:27.627Z
maybe should have included this in the answer. to me wrt this question AKS aligns/ compares against [GNFS](http://en.wikipedia.org/wiki/General_number_field_sieve) which is super- ("non-") polynomial (but subexponential) & seems the other comparisons are apples vs oranges.
vzn
CC BY-SA 3.0
2014-08-04T18:46:24.910Z
What is apples and oranges is comparing AKS (a primality testing algorithm) with GNFS (a factoring algorithm).
Emil Jeřábek
CC BY-SA 3.0
2014-08-04T18:50:16.063Z
ok! feel there is some way to fit this line of thinking/answer _roughly_ to the question (and the citations lead in that direction) but am getting snagged on technicalities and not much constructive help from you.
vzn
CC BY-SA 3.0
2014-08-04T15:31:04.120Z
2014-08-04T16:24:17.653Z
2017-04-13T12:48:30.830Z
vzn
<p>How bout the simplex algorithm for linear programming?
In many occasions <a href="http://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency" rel="noreferrer">it is used</a> in practice.</p>
<p>Edited to add:
I think it's more of a &quot;worse-case exponential algorithm&quot; which runs efficiently on practical <strong>instances/distributions</strong> rather than runs faster on practical <strong>sized</strong> adversarial instances.</p>

CC BY-SA 3.0
2014-08-04T10:51:10.150Z
@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
CC BY-SA 3.0
2014-08-04T06:11:14.950Z
2014-08-10T22:57:15.063Z
2020-06-17T09:38:08.363Z
R B
<p>Do you know of any problems (preferably at least somewhat well known), where, <em>for a practical problem size</em>, an exponential algorithm runs much faster than a best-known polynomial time counterpart.</p>

<p>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 &gt; 15$, the exponential algorithm is preferred.</p>

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

CC BY-SA 3.0
2014-08-04T16:28:50.043Z
I think you might find what you seek in the parameterized complexity literature.
Kaveh
CC BY-SA 3.0
2014-08-04T19:06:08.723Z
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
<time-complexity><polynomial-time><exp-time-algorithms>
Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?
Ozzah
# Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

(Asked by: username_0 on 2014-08-04)

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.

**Tags:** time-complexity, polynomial-time, exp-time-algorithms

> **Comments:**
> **username_1**: I think you might find what you seek in the parameterized complexity literature.  
> **username_2**: 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  

---

## 3 answers

### Answer by username_7 on 2014-08-04. Score: 13 | Accepted answer

How bout the simplex algorithm for linear programming?
In many occasions [it is used](http://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency) 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.

> **Comments:**
> **username_7**: @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".  

---

### Answer by username_3 on 2014-08-11. Score: 12

The [fastest algorithm known](http://arxiv.org/pdf/1109.1030v2.pdf) 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,](http://msp.org/agt/2014/14-03/agt-2014-14-059p.pdf) some of them quite large.

> **Comments:**
> **username_4**: 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.  
> **username_5**: It’s even $O(n^2)$ by http://www.sciencedirect.com/science/article/pii/S0095895611000712 , though I gather the dependence on $|H|$ is still horrible.  
> **username_3**: 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).  

---

### Answer by username_6 on 2014-08-04. Score: -3

There are some examples with (nonprobabilistic/ exact) [primality detection/ testing](http://en.wikipedia.org/wiki/Primality_test). The [AKS algorithm](http://en.wikipedia.org/wiki/AKS_primality_test) 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:

* [When is the AKS primality test actually faster than other tests?](https://cs.stackexchange.com/questions/23260/when-is-the-aks-primality-test-actually-faster-than-other-tests)

> **Comments:**
> **username_5**: 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.  
> **username_6**: Miller-Rabin depends on Riemann Hypothesis variations. etc. AKS first _unconditional_ P-time primality test.  
> **username_5**: The randomized version of Miller–Rabin, which is the one used in practice, does not depend on RH.  
> **username_6**: are you talking about a _probabilistic_ test? as wikipedia states re AKS: _AKS is the first primality-proving algorithm to be simultaneously general, polynomial, deterministic, and unconditional._ therefore other algorithms prior to AKS did not fit all those criteria simultaneously. eg those that were general, deterministic, and unconditional, were not _polynomial_.  
> **username_5**: That’s all very true, but has nothing to do with the original question.  
> **username_6**: ??? eg one of your examples, re same wikipedia entry. "ECPP and APR conclusively prove or disprove that a given number is prime, but are not known to have polynomial time bounds for all inputs." also re your other example, randomized Miller Rabin, "Randomized tests, such as Miller–Rabin and Baillie–PSW, can test any given number for primality in polynomial time, but are known to produce only a probabilistic result."  
> **username_5**: 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).  
> **username_6**: doesnt the answer fit for a slightly less literal/ more broad interpretation of the question re "nonpolynomial" instead of "exponential"?  
> **username_5**: That seriously changes the spirit of the question. There is nothing remarkable on the fact that a randomized polynomial-time algorithm can in practice run faster than a deterministic polynomial-time algorithm for the same problem.  
> **username_6**: maybe should have included this in the answer. to me wrt this question AKS aligns/ compares against [GNFS](http://en.wikipedia.org/wiki/General_number_field_sieve) which is super- ("non-") polynomial (but subexponential) & seems the other comparisons are apples vs oranges.  
> **username_5**: What is apples and oranges is comparing AKS (a primality testing algorithm) with GNFS (a factoring algorithm).  
> **username_6**: ok! feel there is some way to fit this line of thinking/answer _roughly_ to the question (and the citations lead in that direction) but am getting snagged on technicalities and not much constructive help from you.  

---

