15
$\begingroup$

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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, these are very good examples! $\endgroup$
    – Juho
    Commented Jul 11, 2013 at 14:48
  • $\begingroup$ Note that there are very fast known algorithms for primality testing if randomization is allowed. So practically speaking, it doesn't satisfy the criteria that the "fastest known algorithm is slow". $\endgroup$
    – Caleb Stanford
    Commented Mar 25, 2019 at 20:06
11
$\begingroup$

There's a similar question over on cstheory, with lots of examples ranging from the "realistically impractically slow" algorithms with exponents of 6 or 7 upwards. That question also discusses large constants too.

There's one classic that I want to reproduce as it seems like such a spectacularly horrible example of polynomial time (shamelessly stolen from JeffE's answer):

Corollary 1. The number of steps in our algorithm is at most $1752484608000n^{79}L^{25}/D^{26}(\Theta_0)$.

Corollary 2. The number of steps in our algorithm is at most $117607251220365312000n^{79}(\ell_{max}/d_{min}(\Theta_0))^{26}.$

From: Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O’Brien, An Energy-Driven Approach to Linkage Unfolding, SOCG 2004.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I wonder if this is really a practical problem. Also, the list of problems on CSTheory is short, and most of the problems seem pretty esoteric... :-( $\endgroup$
    – Juho
    Commented Jul 11, 2013 at 10:38
  • $\begingroup$ @Juho there's a further link in the first comment on the other question to another similar question on math.se. I found the one I reproduced too amusing to resist, but there are some important ptime results that have terrible algorithms, or non constructive ones: Courcelle's Theorem and a bunch of similar model checking metatheorems, a lot of graph minor things and decomposition algorithm s for properties like treewidth. $\endgroup$
    – Luke Mathieson
    Commented Jul 11, 2013 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.