Problems that are hard to prove in $\mathcal{P}$

Question

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.

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. — usul, Apr 04 '14 at 03:23
Why is matching included ? It's definitely "nontrivially" in P, but it was one of the first ones. — Suresh Venkat, Apr 04 '14 at 05:18
Similar questions Hardest known natural problem in P?, Polynomial-time algorithms with huge exponent/constant — Marzio De Biasi, Apr 04 '14 at 07:23
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... — vzn, Apr 04 '14 at 14:09
@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. — David Richerby, Apr 04 '14 at 23:02
DR will have to try to find a ref describing the situation, believe it is not exactly so simple as questioner hints. afaik the search for "efficient" algorithms to misc problems & matching incl predates the formal definition of P (ie before "efficient" was formally defined) & the search for an efficient matching algorithm may have predated that. the history of algorithms for matching is somewhat complicated, read some acct of it but am not sure where, will have to hunt it down, it might qualify as an answer here, but for some reason unf there is no enthusiasm for this decent question so far :( — vzn, Apr 05 '14 at 02:04

score 15 · Answer 1 · answered Apr 04 '14 at 03:07

15

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

answered Apr 04 '14 at 03:07

user12344567

651
1
5
10

score 12 · Answer 2 · answered Apr 04 '14 at 07:48

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).

score 12 · Accepted Answer · answered Apr 05 '14 at 03:32

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

Nice. this is a good example. – Suresh Venkat Apr 05 '14 at 04:39 — Suresh Venkat, Apr 05 '14 at 04:39

score 6 · Answer 4 · edited Apr 13 '17 at 12:32

6

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.

edited Apr 13 '17 at 12:32

Community

1

answered Apr 04 '14 at 05:12

Phylliida

1,132
5
22

Relative to what? Also exact optimization is not generally in P, as far as I know. – Sasho Nikolov Apr 04 '14 at 06:13
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. – Yoshio Okamoto Apr 04 '14 at 06:30
@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? – Phylliida Apr 04 '14 at 18:00
@Sasho No, exact optimization (in general) is NP Hard, and even slightly non-convex problems become quickly intractable. (assuming P!=NP) – Phylliida Apr 04 '14 at 18:02
@Yoshio Quoting from here: "Convex programs are computationally tractable: there exist numerical methods which efficiently solve every convex program satisfying 'mild' additional assumption; In contrast, no efﬁcient universal methods for nonconvex mathematical programs are known" – Phylliida Apr 04 '14 at 18:07
@Yoshio Though I suppose if Convex Optimization was within P, an algorithm could simply be run to solve a given instance, then if that algorithm ran within am expected amount of time you could tell it was probably convex, whereas if it took too long you could tell that it probably wasn't (thus probably solving an NP-Hard problem). It's possible those fuzzy edges (probably) and "mild" additional assumptions are what cause it to be tractable most of the time, in some approximation way that is usually good enough. Admittedly, I'm not far enough through the course to give more specifics. – Phylliida Apr 04 '14 at 18:19
1

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 :) – Sasho Nikolov Apr 04 '14 at 18:44
You're probably right :) – Phylliida Apr 04 '14 at 18:56
@DaniPhye: It is not about deciding the convexity of an instance. Even if your instance is guaranteed to be convex, the problem is NP-hard. – Yoshio Okamoto Apr 07 '14 at 02:00

score 5 · Answer 5 · edited Apr 13 '17 at 12:19

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).

Problems that are hard to prove in $\mathcal{P}$

5 Answers5

Linked