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

Improve this question
$\endgroup$
6
  • 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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 23:02

5 Answers 5

Reset to default
12
$\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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice. this is a good example. $\endgroup$
    – Suresh Venkat
    Apr 5, 2014 at 4:39
15
$\begingroup$

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

Improve this answer
$\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).

Improve this answer
$\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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Relative to what? Also exact optimization is not generally in P, as far as I know. $\endgroup$
    – Sasho Nikolov
    Apr 4, 2014 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, 2014 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, 2014 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, 2014 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, 2014 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).

Improve this answer
$\endgroup$

Your Answer

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

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