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

CC BY-SA 3.0
2014-04-04T07:48:58.517Z
2014-04-04T07:48:58.517Z
User Mahfud
<p>The famous primality testing problem, shown to be in P in the 2000 paper <a href="http://annals.math.princeton.edu/2004/160-2/p12">PRIMES is in P</a>.</p>

CC BY-SA 3.0
2014-04-04T03:07:19.547Z
2014-04-04T03:07:19.547Z
user12344567
<p><a href="http://en.wikipedia.org/wiki/Convex_optimization" rel="nofollow noreferrer">Convex Optimization</a> is another relatively recent one.</p>

<p>Edit: I suppose more specifically, <a href="http://en.wikipedia.org/wiki/Semidefinite_programming" rel="nofollow noreferrer">Semidefinite Programming</a> is a subfield of convex optimization that has been used in some <a href="http://www.cs.cornell.edu/~dsteurer/talks/siamdm.pdf" rel="nofollow noreferrer">breakthroughs</a> in complexity theory recently.</p>

<p>Edit edit: <a href="https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in?rq=1">This question</a> seemed to cover this point in a little more detail.</p>

CC BY-SA 3.0
2014-04-04T06:13:32.573Z
Relative to what? Also *exact* optimization is not generally in P, as far as I know.
Sasho Nikolov
CC BY-SA 3.0
2014-04-04T06:30:36.803Z
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
CC BY-SA 3.0
2014-04-04T18:00:36.320Z
@Yoshio Hmm, [this course](https://www.youtube.com/watch?v=McLq1hEq3UY) 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
CC BY-SA 3.0
2014-04-04T18:02:05.297Z
@Sasho No, exact optimization (in general) is NP Hard, and even slightly non-convex problems become quickly intractable. (assuming P!=NP)
Phylliida
CC BY-SA 3.0
2014-04-04T18:07:06.177Z
@Yoshio  Quoting from [here](http://homepages.laas.fr/henrion/courses/lmi06/lmiIII1.pdf): "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
CC BY-SA 3.0
2014-04-04T18:19:08.060Z
@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
CC BY-SA 3.0
2014-04-04T18:44:17.997Z
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
CC BY-SA 3.0
2014-04-04T18:56:26.973Z
You're probably right :)
Phylliida
CC BY-SA 3.0
2014-04-07T02:00:49.023Z
@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
CC BY-SA 3.0
2014-04-04T05:12:52.003Z
2014-04-04T20:08:15.757Z
2017-04-13T12:32:28.080Z
Phylliida
<p>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. <a href="http://robertborgersen.info/Presentations/GS-05R-1.pdf" rel="nofollow noreferrer">here</a> or <a href="https://math.stackexchange.com/questions/547096/dilworths-theorem-is-equivalent-to-halls">here</a>).</p>

CC BY-SA 3.0
2014-04-04T22:30:25.000Z
2014-04-04T22:30:25.000Z
2017-04-13T12:19:19.363Z
NisaiVloot
<p>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$.</p>

CC BY-SA 3.0
2014-04-05T04:39:21.840Z
Nice. this is a good example.
Suresh Venkat
CC BY-SA 3.0
2014-04-05T03:32:16.670Z
2014-04-05T03:32:16.670Z
Chandra Chekuri
<p>What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after?</p>

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

<p>Maybe like matching, linear programming. Any list or references would be appreciated.</p>

CC BY-SA 3.0
2014-04-04T03:23:11.857Z
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
CC BY-SA 3.0
2014-04-04T05:18:49.953Z
Why is matching included ? It's definitely "nontrivially" in P, but it was one of the first ones.
Suresh Venkat
CC BY-SA 3.0
2014-04-04T07:23:06.913Z
Similar questions [Hardest known natural problem in P?](http://cstheory.stackexchange.com/questions/20522/hardest-known-natural-problem-in-p), [Polynomial-time algorithms with huge exponent/constant](http://cstheory.stackexchange.com/q/6660/3247)
Marzio De Biasi
CC BY-SA 3.0
2014-04-04T14:09:33.783Z
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
CC BY-SA 3.0
2014-04-04T23:02:31.253Z
@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
CC BY-SA 3.0
2014-04-05T02:04:52.813Z
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
<reference-request><big-list><polynomial-time>
Problems that are hard to prove in $\mathcal{P}$
zighalo
# Problems that are hard to prove in $\mathcal{P}$

(Asked by: username_0 on 2014-04-04)

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.

**Tags:** reference-request, big-list, polynomial-time
> **Comments:**
> **username_1**: 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.  
> **username_2**: Why is matching included ? It's definitely "nontrivially" in P, but it was one of the first ones.  
> **username_3**: Similar questions [Hardest known natural problem in P?](http://cstheory.stackexchange.com/questions/20522/hardest-known-natural-problem-in-p), [Polynomial-time algorithms with huge exponent/constant](http://cstheory.stackexchange.com/q/6660/3247)  
> **username_4**: 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...  
> **username_5**: @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**.  
> **username_4**: 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 :(  

---

## 5 answers

### Answer by username_12 on 2014-04-05. Score: 12 | Accepted answer

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

> **Comments:**
> **username_2**: Nice. this is a good example.  

---

### Answer by username_7 on 2014-04-04. Score: 15

The famous primality testing problem, shown to be in P in the 2000 paper [PRIMES is in P](http://annals.math.princeton.edu/2004/160-2/p12).


---

### Answer by username_6 on 2014-04-04. Score: 12

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


---

### Answer by username_8 on 2014-04-04. Score: 6

[Convex Optimization](http://en.wikipedia.org/wiki/Convex_optimization) is another relatively recent one.

Edit: I suppose more specifically, [Semidefinite Programming](http://en.wikipedia.org/wiki/Semidefinite_programming) is a subfield of convex optimization that has been used in some [breakthroughs](http://www.cs.cornell.edu/~dsteurer/talks/siamdm.pdf) in complexity theory recently.

Edit edit: [This question](https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in?rq=1) seemed to cover this point in a little more detail.

> **Comments:**
> **username_9**: Relative to what? Also *exact* optimization is not generally in P, as far as I know.  
> **username_10**: 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.  
> **username_8**: @Yoshio Hmm, [this course](https://www.youtube.com/watch?v=McLq1hEq3UY) 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?  
> **username_8**: @Sasho No, exact optimization (in general) is NP Hard, and even slightly non-convex problems become quickly intractable. (assuming P!=NP)  
> **username_8**: @Yoshio  Quoting from [here](http://homepages.laas.fr/henrion/courses/lmi06/lmiIII1.pdf): "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"  
> **username_8**: @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.  
> **username_9**: 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 :)  
> **username_8**: You're probably right :)  
> **username_10**: @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.  

---

### Answer by username_11 on 2014-04-04. Score: 5

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](http://robertborgersen.info/Presentations/GS-05R-1.pdf) or [here](https://math.stackexchange.com/questions/547096/dilworths-theorem-is-equivalent-to-halls)).


---

