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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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