<p>How bout <a href="http://ac.els-cdn.com/S0166218X97001212/1-s2.0-S0166218X97001212-main.pdf?_tid=11728ab4-be80-11e3-9e7c-00000aacb361&amp;acdnat=1396894481_d7c17dcda37aaade0c9ed6c63e7c7bc7">finding two disjoint shortest paths</a>, which has a runtime of $O(|V|^8)$?</p>

<p>Also, $O(|V|^{12}\cdot |E|)$ algorithm <a href="http://www.ii.uib.no/~martinv/Papers/ISinP5free.pdf">is known</a> for independent set in $P_5$-free graphs.</p>

CC BY-SA 3.0
2014-04-07T18:14:51.817Z
2014-10-01T07:56:10.160Z
2014-10-01T07:56:10.160Z
R B
<p>The <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow">AKS Primality testing algorithm</a> may be a good candidate, where the best algorithm currently known version of the algorithm has $\tilde{O}(n^6)$ running time.  See <a href="http://www.math.dartmouth.edu/~carlp/aks041411.pdf" rel="nofollow">Primality testing with Gaussian periods</a> (Lenstra and Pomerance).</p>

CC BY-SA 3.0
2014-01-09T18:22:52.427Z
2014-10-02T23:18:21.327Z
2014-10-02T23:18:21.327Z
Shaull
<p><a href="http://en.wikipedia.org/wiki/Perfect_graph">perfect graphs</a> appear to be fundamental and therefore "natural" to complexity theory/math in many ways. the <a href="http://integer.tepper.cmu.edu/webpub/BergeAlg.pdf">recognition algorithm</a> runs in time $O(|V(G)|^9)$. it seems possible there are other "natural" or "fundamental" graph classes that take longer to recognize and are still in P.</p>

CC BY-SA 3.0
2014-04-08T16:55:46.777Z
note perfect graphs are based on optimizing/maximizing the [Shannon (communication) capacity of graphs](http://mathworld.wolfram.com/ShannonCapacity.html); see also [why are perfect graphs called perfect](http://cstheory.stackexchange.com/questions/14414/)
vzn
CC BY-SA 3.0
2014-02-28T02:33:13.547Z
2014-02-28T02:33:13.547Z
vzn
<p>I wonder, what is (currently) the largest number $k$, such that a <em>natural</em> problem is known with the following properties:</p>

<ol>
<li><p>An $O(n^k)$ algorithm has been already found for the problem.</p></li>
<li><p>For any fixed $\epsilon&gt;0$ no $O(n^{k-\epsilon})$ algorithm is known for the same problem. (Note that a faster algorithm $may$ exist, just it is not known yet, so I am not looking for a proven lower bound.)</p></li>
<li><p>The problem description itself does not depend on $k$. (This condition is needed to exclude parametrized cases like "find a clique of size $k$ in an input graph, for a constant $k$.")</p></li>
</ol>

<p>In a sense, such a problem might qualify as the <em>hardest, known, natural, problem</em> in $\bf P$ (regarding the exponent of the fastest known algorithm).</p>

CC BY-SA 3.0
2014-01-09T18:34:09.157Z
Try this maybe? http://cstheory.stackexchange.com/q/6660/1800
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-01-09T19:44:03.437Z
Thank you, I was not aware of that post. It has plenty of interesting answers.
Andras Farago
CC BY-SA 3.0
2014-01-09T19:49:24.670Z
Another related post is http://cs.stackexchange.com/questions/13202/decision-problems-in-mathsfp-without-fast-algorithms
vb le
CC BY-SA 3.0
2014-02-27T16:42:06.600Z
matrix multiplication exponent could fit as an answer?
Turbo
<cc.complexity-theory><ds.algorithms>
Hardest known natural problem in P?
Andras Farago
# Hardest known natural problem in P?

(Asked by: username_0 on 2014-01-09)

I wonder, what is (currently) the largest number $k$, such that a *natural* problem is known with the following properties:

1. An $O(n^k)$ algorithm has been already found for the problem.
2. For any fixed $\epsilon>0$ no $O(n^{k-\epsilon})$ algorithm is known for the same problem. (Note that a faster algorithm $may$ exist, just it is not known yet, so I am not looking for a proven lower bound.)
3. The problem description itself does not depend on $k$. (This condition is needed to exclude parametrized cases like "find a clique of size $k$ in an input graph, for a constant $k$.")

In a sense, such a problem might qualify as the *hardest, known, natural, problem* in $\bf P$ (regarding the exponent of the fastest known algorithm).

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: Try this maybe? http://cstheory.stackexchange.com/q/6660/1800  
> **username_0**: Thank you, I was not aware of that post. It has plenty of interesting answers.  
> **username_2**: Another related post is http://cs.stackexchange.com/questions/13202/decision-problems-in-mathsfp-without-fast-algorithms  
> **username_3**: matrix multiplication exponent could fit as an answer?  

---

## 3 answers

### Answer by username_5 on 2014-01-09. Score: 27

The [AKS Primality testing algorithm](http://en.wikipedia.org/wiki/AKS_primality_test) may be a good candidate, where the best algorithm currently known version of the algorithm has $\tilde{O}(n^6)$ running time. See [Primality testing with Gaussian periods](http://www.math.dartmouth.edu/~carlp/aks041411.pdf) (Lenstra and Pomerance).


---

### Answer by username_4 on 2014-04-07. Score: 16

How bout [finding two disjoint shortest paths](http://ac.els-cdn.com/S0166218X97001212/1-s2.0-S0166218X97001212-main.pdf?_tid=11728ab4-be80-11e3-9e7c-00000aacb361&acdnat=1396894481_d7c17dcda37aaade0c9ed6c63e7c7bc7), which has a runtime of $O(|V|^8)$?

Also, $O(|V|^{12}\cdot |E|)$ algorithm [is known](http://www.ii.uib.no/~martinv/Papers/ISinP5free.pdf) for independent set in $P\_5$-free graphs.


---

### Answer by username_6 on 2014-02-28. Score: 13

[perfect graphs](http://en.wikipedia.org/wiki/Perfect_graph) appear to be fundamental and therefore "natural" to complexity theory/math in many ways. the [recognition algorithm](http://integer.tepper.cmu.edu/webpub/BergeAlg.pdf) runs in time $O(|V(G)|^9)$. it seems possible there are other "natural" or "fundamental" graph classes that take longer to recognize and are still in P.

> **Comments:**
> **username_6**: note perfect graphs are based on optimizing/maximizing the [Shannon (communication) capacity of graphs](http://mathworld.wolfram.com/ShannonCapacity.html); see also [why are perfect graphs called perfect](http://cstheory.stackexchange.com/questions/14414/)  

---

