4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}})$. $\endgroup$ – David Richerby Sep 26 '18 at 10:32
  • $\begingroup$ 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. $\endgroup$ – Thinh D. Nguyen Sep 26 '18 at 10:43
  • $\begingroup$ 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}})$. $\endgroup$ – David Richerby Sep 26 '18 at 10:51
  • 1
    $\begingroup$ 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$. $\endgroup$ – kne Sep 26 '18 at 13:11
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thinh D. Nguyen Sep 26 '18 at 13:55
  • $\begingroup$ @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. $\endgroup$ – Nat Sep 26 '18 at 13:59
1
$\begingroup$

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

$\endgroup$

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.