What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known algorithm is "slow".
Here are two examples:
Recognition of perfect graphs. In their FOCS'03 paper [1] Cornuéjols, Liu and Vuskovic gave an $O(n^{10})$ time algorithm for the problem, where $n$ is the number of vertices. I'm not sure if this bound has been improved upon, but as I understand it, more or less a breakthrough is needed to obtain a faster algorithm. (The authors give an $O(n^9)$ time algorithm in the journal version of [1], see here).
Recognition of map graphs. Thorup [2] gave a rather complex algorithm with the exponent being (about?) $120$. Perhaps this has been even dramatically improved upon, but I don't have a good reference.
I'm especially interested in problems that have practical importance, and obtaining a "fast" (or even a practical) algorithm has been open for several years.
[1] Cornuéjols, Gérard, Xinming Liu, and Kristina Vuskovic. "A polynomial algorithm for recognizing perfect graphs." Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on. IEEE, 2003.
[2] Thorup, Mikkel. "Map graphs in polynomial time." Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on. IEEE, 1998.
Asked By : Juho
Answered By : vb le
Perhaps the following problems fit into your examples:
(The decision version of) Coloring, Clique, Stable Set, Clique Covering in perfect graphs. So far, the only known polynomial time algorithms for these problems are based on the ellipsoid method, which is ''slow'' (and numerically unstable).
AKS-primality test in $O((\log n)^{12})$ time. Though many improvements (currently $O((\log n)^{7.5})$), the AKS-algorithm is still too slow in practice.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13202
0 comments:
Post a Comment
Let us know your responses and feedback