Recently I wrote a blog post entitled "The Scientific Case for P≠NP". The argument I tried to articulate there is that there seems to be an "invisible electric fence" separating the problems in P from the NP-complete ones, and that this phenomenon should increase our confidence that P≠NP. So for example, the NP-complete Set Cover problem is approximable in polynomial time to within a factor of ln(n), but is NP-hard to approximate to within an even slightly smaller factor (say, 0.999ln(n)). Notice that, if either the approximation algorithm or the hardness result had been just slightly better than it was, then P=NP would've followed immediately. And there are dozens of other examples like that. So, how do our algorithms and our NP-hardness results always manage to "just avoid" crossing each other, even when the avoidance requires that they "both know about" some special numerical parameter? To me, this seems much easier to explain on the P≠NP hypothesis than on the P=NP one.

Anyway, one of the questions that emerged from the discussion of that post was sufficiently interesting (at least to me) that I wanted to share it on MO.

The question is this: When, in the history of mathematics, have problems "like P vs. NP" arisen and then been solved? In those cases, what were the resolutions?

I'd better clarify what I mean by a problem being "like P vs. NP"! I mean the following:

(1) Mathematicians managed to classify a large number of objects of interest to them into two huge classes. (Ideally, these would be two equivalence classes, like P and the NP-complete problems, which they conjectured to be disjoint. But I'd settle for two classes one of which clearly contains the other, like P and NP, as long as many of the objects conjectured to be in $\operatorname{Class}_2 \setminus \operatorname{Class}_1$ were connected to each other by a complex web of reductions, like the NP-complete problems are---so that putting one of these objects in $\operatorname{Class}_1$ would also do so to many others.)

(2) Mathematicians conjectured that the two classes were unequal, but were unable to prove or disprove that for a long time, even as examples of objects in the two classes proliferated.

(3) Eventually, the conjecture was either proved or disproved.

(4) Prior to the eventual solution, the two classes appeared to be separated by an "invisible fence," in the same sense that P and the NP-complete problems are. In other words: there were many results that, had they been slightly different (say, in some arbitrary-looking parameter), would have collapsed the two classes, but those results always stopped short of doing so.

To give a sense of what I have in mind, here are the best examples we've come up with so far (I'd say that they satisfy some of the conditions above, but probably not all of them):

• David Speyer gave the example of Diophantine sets of integers versus recursively enumerable sets. The former was once believed to be a proper subset of the latter, but now we know they're the same.

• Sam Hopkins gave the example of symplectic manifolds versus Kähler manifolds. The former contains the latter, but the containment was only proved to be strict by Thurston in the 1970s.

• I gave the example of independence results in set theory. Until Cohen, there were many proven statements about transfinite sets, and then a whole class of other statements---V=L, GCH, CH, AC, Zorn's Lemma, well-orderability...---that were known to be interrelated by a web of implications (or equivalent, as in the last three cases), but had resisted all proof attempts. Only with forcing were the two classes "separated," an outcome that some (like Gödel) had correctly anticipated.