# Highest order poly-time algorithm that efficiently solves an interesting problem?
**URL:** https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287
**Category:** Factual Questions
**Created:** [March 28, 2006, 8:10pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287 "2006-03-28T20:10:38Z")
**Posts on this page:** 14
**Page:** 1
### Author:  [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)
#### Post date: [March 28, 2006, 8:10pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/1 "2006-03-28T20:10:38Z")
The slashdot poll today was on whether people think P==NP, and someone rightly brought up that, even if P==NP, it’s quite possible that the poly-time algorithm for NP problems will be slow enough that it won’t really make much of a difference. If we discover an O(n[sup]100[/sup]) algorithm that solves NP-complete problems, it won’t make much of a difference as far as practical computation goes.
But that made me wonder: What is the highest-order polynomial algorithm that is the most efficient solution to an interesting problem? In school, I only remember learning about algorithms that were n[sup]3[/sup] at worst, and the vast majority of the algirhtms we learned were n[sup]2[/sup] or better. I would define _interesting_ in this case to mean having a practical application, not just mathematical interest. I realize that “purely” mathematical problems often do end up having a practical application, but I’m hoping to avoid the trivial answer of “standard algorithm applied in a k-dimensional space” which (may) have an O(n[sup]k[/sup]) running time.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [March 28, 2006, 8:20pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/2 "2006-03-28T20:20:40Z")
It’s hard to call an [symbol]w/symbol algorithm efficient, don’t you think?
---
### Author:  [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)
#### Post date: [March 28, 2006, 9:05pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/3 "2006-03-28T21:05:00Z")
It depends on the problem. n[sup]2[/sup] is the runtime of an inefficient sorting algorithm, but n[sup]2.71[/sup] (or whatever it is) is the runtime of an efficient matrix multiplication algorithm.
---
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [March 28, 2006, 9:14pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/4 "2006-03-28T21:14:28Z")
> [@iamthewalrus(:3=](#):
>
> It depends on the problem. n[sup]2[/sup] is the runtime of an inefficient sorting algorithm, but n[sup]2.71[/sup] (or whatever it is) is the runtime of an efficient matrix multiplication algorithm.
Actually, n[sup]2[/sup] is the runtime for the kinds of sorting algorithms that most people can come up with. It takes a real computer scientist to invent a **really** inefficient sorting algorithm:
```auto
while A not sorted
permute(A)
```
_O_(n!) 🙂
---
### Author:  [@ftg](https://boards.straightdope.com/u/ftg)
#### Post date: [March 28, 2006, 9:22pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/5 "2006-03-28T21:22:17Z")
Many NP-complete problems are solvable in poly time when a key parameter is fixed. But that parameter then appears in the exponent of the running time. Take determining whether a graph can be embedded on a surface of a given fixed genus g (how many “doughnut holes” it has). There’s a classic linear time algorithm for the plane. Keep increasing g and the exponent in the running time keeps going up. The running time of the Miller, Filotti, and Reif algorithm is O(v[sup]0(g)[/sup]) for a graph with v nodes.
There are also parameterized versions of many NP-hard optimization problems. E.g., if you want to get within X% of optimum for bin-packing, the running time will have an exponent that is inversely related to X. I.e., the better answer you want, the more running time is needed. (Hardly a shock.) A little bit of info [here](http://en.wikipedia.org/wiki/Approximation_algorithm).
(Many, many NP-complete problems cannot be solved like this though. E.g., coloring a graph and finding a longest non-intersecting path.)
In short, there is no “practical” limit on the exponent for poly time algorithms.
As to specific non-NP related problems, there have been some really fair sized exponents for problems like max flow that eventually got worked down to something more manageable.
Note that all this applies to _algorithms_ and not to _problems_. There are virtually no tight non-trivial lower bounds for problems.
Go get some recent STOC and FOCS proceedings and I’m sure you’ll see some new algorithms that have nice sized exponents.
---
### Author:  [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)
#### Post date: [March 28, 2006, 9:53pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/6 "2006-03-28T21:53:27Z")
Thanks, **ftg**.
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [March 29, 2006, 5:09am UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/7 "2006-03-29T05:09:34Z")
> [@](#):
>
> Take determining whether a graph can be embedded on a surface of a given fixed genus g (how many “doughnut holes” it has). There’s a classic linear time algorithm for the plane. Keep increasing g and the exponent in the running time keeps going up. The running time of the Miller, Filotti, and Reif algorithm is O(v[sup]0(g)[/sup]) for a graph with v nodes.
This seems counterintuitive to me… I would expect that for any number of nodes v, there is some g such that a surface of genus g can accomodate all graphs with v nodes, and I would expect the bounds for the required g to be calculable. In fact, I can trivially embed a complete graph of v vertices on a surface of genus g = v\*(v-1). So for any g \> v\*(v-1), the answer “yes” can be given almost instantly.
---
### Author:  [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)
#### Post date: [March 29, 2006, 2:08pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/8 "2006-03-29T14:08:04Z")
> [@Punoqllads](#):
>
> Actually, n[sup]2[/sup] is the runtime for the kinds of sorting algorithms that most people can come up with. It takes a real computer scientist to invent a **really** inefficient sorting algorithm:
>
> ```auto
>
> while A not sorted
> permute(A)
>
> ```
>
> _O_(n!) 🙂
On the plus side, it’s only O(n) best case 😃
---
### Author:  [@Mathochist](https://boards.straightdope.com/u/Mathochist)
#### Post date: [March 29, 2006, 2:47pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/9 "2006-03-29T14:47:16Z")
> [@Chronos](#):
>
> This seems counterintuitive to me… I would expect that for any number of nodes v, there is some g such that a surface of genus g can accomodate all graphs with v nodes, and I would expect the bounds for the required g to be calculable. In fact, I can trivially embed a complete graph of v vertices on a surface of genus g = v\*(v-1). So for any g \> v\*(v-1), the answer “yes” can be given almost instantly.
Possibly the MFR alagorithm doesn’t take that case into account?
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [March 29, 2006, 3:02pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/10 "2006-03-29T15:02:11Z")
> [@Chronos](#):
>
> This seems counterintuitive to me… I would expect that for any number of nodes v, there is some g such that a surface of genus g can accomodate all graphs with v nodes, and I would expect the bounds for the required g to be calculable. In fact, I can trivially embed a complete graph of v vertices on a surface of genus g = v\*(v-1). So for any g \> v\*(v-1), the answer “yes” can be given almost instantly.
That’s consistent with the O notation given. Remember that saying that f is O(g) just means that there’s some constants N and c such that f(n) \< cg(n) when n \> N. As long as k \> 0, 1 is O(n[sup]k[/sup]).
---
### Author:  [@ftg](https://boards.straightdope.com/u/ftg)
#### Post date: [March 29, 2006, 4:44pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/11 "2006-03-29T16:44:10Z")
**Chronos** : Note that I said “of a given **fixed** genus g”. g is a input to the problem.
E.g., you can always color a graph with v nodes with v colors. The NP-complete question is “Can you color this graph with this number of colors?” Two inputs: graph and number of colors.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [March 29, 2006, 5:21pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/12 "2006-03-29T17:21:26Z")
> [@ftg](#):
>
> **Chronos** : Note that I said “of a given **fixed** genus g”. g is a input to the problem.
>
> E.g., you can always color a graph with v nodes with v colors. The NP-complete question is “Can you color this graph with this number of colors?” Two inputs: graph and number of colors.
To **Chronos** ’s point, for sufficiently high values of the input g, the answer can be given much more quickly than the asymptotic running time indicates. But since O allows for very loose upper bounds, it’s not a problem.
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [March 29, 2006, 7:09pm UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/13 "2006-03-29T19:09:33Z")
I think I see my mistake… O only cares about the limit for very large problems. And for v larger than sqrt(g), the trivialization I noted doesn’t apply, and it’s the large v that are important (what v constitutes “large” depends, of course, on the given value of g). So even though, for large g, there’s an awful lot of easy values of v, the difficulty could sharply increase past some threshhold, thus making the problem, for large g, asymptotically “hard”.
---
### Author:  [@ftg](https://boards.straightdope.com/u/ftg)
#### Post date: [March 30, 2006, 4:51am UTC](https://boards.straightdope.com/t/highest-order-poly-time-algorithm-that-efficiently-solves-an-interesting-problem/350287/14 "2006-03-30T04:51:56Z")
I misspoke: Genus g is not an actual imput. It is a specification of the problem. So a program to solve it would have g hardcoded in it. Only the graph is the input. But a program with a small g will run faster than a program with a large g.