What are some problems that are in $\mathrm{P}$ but the best known algorithm has a high-degree polynomial ($\ge 3$) time complexity?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Possible duplicate of Decision problems in $\mathsf{P}$ without fast algorithms $\endgroup$– JuhoSep 27, 2018 at 9:36
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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.
answered Sep 26, 2018 at 7:34
-
$\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$ Sep 26, 2018 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$ Sep 26, 2018 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$ Sep 26, 2018 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$– kneSep 26, 2018 at 13:11
$\begingroup$
$\endgroup$
2
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 .$
-
$\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$ Sep 26, 2018 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$– NatSep 26, 2018 at 13:59
$\begingroup$
$\endgroup$
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$.)
