# Hardest known natural problem in P?

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).

• Try this maybe? cstheory.stackexchange.com/q/6660/1800 Jan 9, 2014 at 18:34
• Thank you, I was not aware of that post. It has plenty of interesting answers. Jan 9, 2014 at 19:44
• Another related post is cs.stackexchange.com/questions/13202/… Jan 9, 2014 at 19:49
• matrix multiplication exponent could fit as an answer? Feb 27, 2014 at 16:42

The AKS Primality testing algorithm 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 (Lenstra and Pomerance).
How bout finding two disjoint shortest paths, which has a runtime of $O(|V|^8)$?
Also, $O(|V|^{12}\cdot |E|)$ algorithm is known for independent set in $P_5$-free graphs.
perfect graphs appear to be fundamental and therefore "natural" to complexity theory/math in many ways. the recognition algorithm 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.