3
$\begingroup$

What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after?

I want to know a list of problems that are difficult to prove in the class of "easy" problems?

Maybe like matching, linear programming. Any list or references would be appreciated.

$\endgroup$
  • 4
    $\begingroup$ I feel like there was a similar question along the lines of "problems that took a long time to show in P", but I haven't been able to find it yet. $\endgroup$ – usul Apr 4 '14 at 3:23
  • 4
    $\begingroup$ Why is matching included ? It's definitely "nontrivially" in P, but it was one of the first ones. $\endgroup$ – Suresh Venkat Apr 4 '14 at 5:18
  • 4
    $\begingroup$ Similar questions Hardest known natural problem in P?, Polynomial-time algorithms with huge exponent/constant $\endgroup$ – Marzio De Biasi Apr 4 '14 at 7:23
  • $\begingroup$ afaik historically spking there was a quite a bit of study on matching before it was shown to be in P, and there was a period of uncertainty (ie generally recognized as open problem at time), and some were surprised by it proved in P, although it was decades ago... $\endgroup$ – vzn Apr 4 '14 at 14:09
  • 5
    $\begingroup$ @vzn The complexity class P dates from about 1965. Edmonds' perfect matching algorithm for general graphs dates from 1961 (though wasn't published until 1965). So it was never an open problem whether matchings is in P. $\endgroup$ – David Richerby Apr 4 '14 at 23:02
11
$\begingroup$

The $k$-disjoint path problem for fixed $k$. Given an undirected graph $G$ and $k$ node pairs $s_1t_1,s_2t_2,\ldots,s_kt_k$, are there node-disjoint paths in $G$ connecting the pairs? Polynomial-time algorithm follows from the work of Robertson and Seymour and relies on very non-trivial and difficult graph theoretic results. There are more general problems than this one but the disjoint paths problem is highly non-trivial even for $k=2$. For instance it is NP-Complete in directed graphs for $k=2$.

$\endgroup$
  • $\begingroup$ Nice. this is a good example. $\endgroup$ – Suresh Venkat Apr 5 '14 at 4:39
14
$\begingroup$

The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.

$\endgroup$
12
$\begingroup$

Testing perfect graphs. Famous people (Lovasz, Knuth, ...) conjectured in the 1980s that there is a polynomial time recognition for perfect graphs. Such an algorithm was found after almost 20 years later by famous people ( Cornuéjols and other, FOCS 2003).

$\endgroup$
6
$\begingroup$

Convex Optimization is another relatively recent one.

Edit: I suppose more specifically, Semidefinite Programming is a subfield of convex optimization that has been used in some breakthroughs in complexity theory recently.

Edit edit: This question seemed to cover this point in a little more detail.

$\endgroup$
  • $\begingroup$ Relative to what? Also exact optimization is not generally in P, as far as I know. $\endgroup$ – Sasho Nikolov Apr 4 '14 at 6:13
  • $\begingroup$ Convex optimization is NP-hard. For example, it is coNP-complete to determine a given matrix is copositive, and the set of all copositive matrices (of given size) forms a closed convex cone. $\endgroup$ – Yoshio Okamoto Apr 4 '14 at 6:30
  • $\begingroup$ @Yoshio Hmm, this course seemed to give the impression that is was as solved as linear programming. Maybe is it NP-hard to determine whether or something is convex (like the example you gave), yet within P for actually solving the problem once you prove that? $\endgroup$ – Phylliida Apr 4 '14 at 18:00
  • $\begingroup$ @Sasho No, exact optimization (in general) is NP Hard, and even slightly non-convex problems become quickly intractable. (assuming P!=NP) $\endgroup$ – Phylliida Apr 4 '14 at 18:02
  • 1
    $\begingroup$ The mildest assumptions that work AFAIK are a separation oracle for the convex set, or a membership oracle and a point strictly inside the set (sufficiently far away from all boundaries). And even under these assumptions, exact optimization is possible only for LP problems. Even for SDPs you need to be very careful. Maybe you need to make your way through the course before you give an answer :) $\endgroup$ – Sasho Nikolov Apr 4 '14 at 18:44
5
$\begingroup$

There are some interesting problems in combinatorial optimization whose membership in $\sf{P}$ is quite non-trivial, in particular it often relies on some deep min-max theorem. Some examples are problems involving graphs (non-bipartite matching, maximum flow, and some of their extensions), posets (max antichain, max union of $k$ chains, path cover...), or matroids (intersection, partitioning, parity...). Afaik none of these problems are believed to be $\sf{P}$-complete though, but some of them are known to be equivalent (see e.g. here or here).

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