34

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

vzn
  • 11,014
  • 2
  • 31
  • 64
Andras Farago
  • 11,396
  • 37
  • 70

3 Answers3

27

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

D.W.
  • 12,054
  • 2
  • 34
  • 80
Shaull
  • 5,571
  • 1
  • 22
  • 32
16

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.

R B
  • 9,448
  • 5
  • 34
  • 74
13

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.

vzn
  • 11,014
  • 2
  • 31
  • 64