patternMinor
What are some problems in $\mathrm{P}$ with time complexity of high-degree polynomial?
Viewed 0 times
degreemathrmwhatpolynomialarewithhightimesomeproblems
Problem
What are some problems that are in $\mathrm{P}$ but the best known algorithm has a high-degree polynomial ($\ge 3$) time complexity?
Solution
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.
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.
Context
StackExchange Computer Science Q#97784, answer score: 2
Revisions (0)
No revisions yet.