# What are some problems in $\mathrm{P}$ with time complexity of high-degree polynomial?

What are some problems that are in $$\mathrm{P}$$ but the best known algorithm has a high-degree polynomial ($$\ge 3$$) time complexity?

Concrete example: Thorup's $$O(n^{120})$$ time algorithm to recognize half-squares of planar bipartite graphs.

https://arxiv.org/abs/1804.05793

Parameterized problem: Some parameterized $$NP$$-complete problems have arbitrarily large polynomial time algorithms. Like, finding a $$k$$-clique in a graph can be solved by $$\Theta(n^k)$$ algorithm. And we do not know how to do much better. There might be some improvement but in general when the parameter increases the degree of the polynomial run-time bound increases also.

Computational geometry problems parameterized with the number of dimensions $$d$$ can be seen as a special case in this group.

Some other $$NP$$-complete problems (like Vertex Cover in the comment of kne below) have parameterized version with linear-time algorithm for each parameter value. So, it takes some careful investigations before naming a hard parameterized problems.

• OK, but really we're looking for $\Omega$ bounds, here. For example, we can correctly say that mergesort has running time $O(n^{10^{10}})$. – David Richerby Sep 26 '18 at 10:32
• From the OP's words "but the best known algorithm has...", so this question is about current status a.k.a. state of the art. – Thinh D. Nguyen Sep 26 '18 at 10:43
• Yes, it's about state of the art. But we're still looking for $\Omega$ bounds. Mergesort is the state of the art and it has running time $O(n^{10^{10}})$. – David Richerby Sep 26 '18 at 10:51
• The part about parameterized problems is not quite correct. There are NP-complete problems whose parameterized version is in FPT. The classical example is Vertex Cover, which has a linear algorithm for each $k$. – kne Sep 26 '18 at 13:11

What are some problems that are in $$\mathrm{P}$$ but the best known algorithm has a high-degree polynomial ($$\ge 3$$) time complexity?

Polynomial time always makes me think of nested loops, such that $$\ge \operatorname{O}\left(n^3\right)$$ looks like "nest three-or-more loops".

So, optimizing $$f\left(x_0 , \, x_1 , \, \dots , \,x_m \right) ,$$ where:

• $$f$$ is a black-box function;

• each $$x_i$$ has $$n$$ distinct values; and

• $$m \ge 2 .$$

• This is not a decision problem belonging to $\mathrm{P}$. Black-box algorithms are used in other situation when one wants to model a class of algorithms each with the black box replaced by a concrete function. So, you may need to find a hard-enough fuonction $f$ to make your answer helpful. – Thinh D. Nguyen Sep 26 '18 at 13:55
• @ThinhD.Nguyen Having $f$ being defined as a crypto-hash of the concatenation of the inputs' serializations and then interpreted as a binary integer to be maximized, and the crypto-hash is extended as $n$ and $m$ grow, would seem like an easy example. However, could you elaborate on the concern about black-box functions? I mean, it's unclear to me what the concern is. – Nat Sep 26 '18 at 13:59

For an integer $$k$$, let $$P_k$$ be the following problem: The input is a program $$p$$ in your favourite programming language. The question is whether $$p$$ halts after at most $$|p|^k$$ steps, where $$|p|$$ is the input size (the length of the program $$p$$). Unless the chosen programming language is very unusual, every $$P_k$$ is decidable in polynomial time; yet for every exponent $$e$$, there is some $$k$$ such that $$P_k$$ requires $$\Omega(n^e)$$ time. This is an application of the time hierarchy theorem.

The above is an academic example. It is stronger than what you asked for: Not only the best known algorithm has a high exponent; all possible algorithms do. An example for a natural problem with a high-ish best-known exponent is primality. There, as far as I know, the exponent is $$6$$. (To be precise: This is the best known exponent for algorithm. The actual exponent might be lower. In fact, the first estimate for the same algorithm had an exponent of $$12$$.)