Analogues of P vs. NP in the history of mathematics

Question

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.

Answer 1

This isn't an exact analogue to P != NP, in which two large classes exist and it is undecided whether they are equal or not; instead, two large "universes" exist, of which only one is the truth, with one of them strongly believed to not exist, but for which all attempts to disprove this parallel universe have been defeated by an invisible fence. (Perhaps a complexity theory analogue would be a scenario in which we knew that of Impagliazzo's five worlds, only Algorithmica or Cryptomania were possible, but we could not determine which, with both worlds showing an equal propensity to "want to exist".)

Anyway, the situation is in analytic number theory, where there are two worlds (which, very roughly, would correspond to "Algorithmica" and "Cryptomania" in Impagliazzo's list):

• Siegel zero: The primes conspire (i.e. show extremely anomalous correlation) with some multiplicative function, such as a Dirichlet character $\chi$; roughly speaking, this means that there is some modulus q such that there is a huge bias amongst the primes to be quadratic nonresidues mod q rather than quadratic residues. (Dirichlet's theorem tells us that the bias will die down eventually - for primes exponentially larger than q - but this is not useful in many applications). The most common way to describe this scenario is through a "Siegel zero" - a zero of an L-function that is really, really far away from the critical line (and really close to 1). Weirdly, such a conspiracy actually makes many number theory problems about the primes easier than harder, because one gets to "pretend" that the Mobius function is essentially a character. For instance, there is a cute result of Heath-Brown that if there are an infinite family of Siegel zeroes, then the twin prime conjecture is true. (Basically, the principle is that at most one conspiracy in number theory can be in force for any given universe; a Siegel zero conspiracy sucks up all the "conspiracy oxygen" for a twin prime conspiracy to also hold.) It does lead to some other weird behaviour though; for instance, the existence of a Siegel zero forces many of the zeroes of the Riemann zeta function to lie on the critical line and be almost in arithmetic progression.

• Standard model: this is the universe which is believed to exist, in which the primes do not exhibit any special correlation with any other standard multiplicative function. In this world, GRH is believed to be true (and the zeroes should be distributed according to GUE, rather than in arithmetic progressions (this latter hypothesis has occasionally been called the "Alternative hypothesis")).

[This is an oversimplification; much as how complexity theorists have not ruled out the intermediate worlds between Algorithmica and Cryptomania, we don't have as strong of a separation between these two number-theoretic worlds as we would like. For instance there could conceivably be intermediate worlds where there are no Siegel zeroes, but GRH or GUE still fails (somewhat analogous to Impagliazzo's "Pessiland"). So in practice we have to weaken one or the other of these worlds, for instance by replacing GRH with a much weaker zero-free region. I'm glossing over these technical details though for this discussion. My feeling is that we have some chance with current technology of eliminating some more of these intermediate worlds, but we're quite stuck on eliminating either of the extreme worlds.]

In many different problems in analytic number theory, one has to split into two cases depending on which of the above universes is actually the one we live in, and use different arguments for each (which is the major source of the notorious ineffectivity phenomenon in analytic number theory, that many of out estimates involve completely ineffective constants, as they could depend on the conductor of a Siegel zero, for which we have no upper bound); finding a way around this dichotomy in even just one of these problems would be a huge breakthrough and would likely lead soon to the elimination of one of these universes from consideration. But there is an invisible fence that seems to block us from doing so; both universes exhibit a surprising amount of "self-consistency", suggesting that one could modify our mathematical universe very slightly one way or the other to "force" one of the two scenarios to be in effect (a bit like how one can force P to equal or not equal NP by relativising). The "parity barrier" in sieve theory is one big (and relatively visible) section of this fence, but this fence seems to be much longer and more substantial than just this parity barrier.

I discuss these things a bit more in this blog post. See also this survey of Conrey that was also linked to above.

Answer 2

The set of theorems in (what now we call) "absolute geometry" and the set of theorems of "euclidean geometry". That is, the history of the parallel postulate. We now know (after Tarski's formalization of "elementary" geometry) that every (first order) euclidean but not absolute statement has a "NP-complete like" role (and its negation has the same separation role for absolute and hyperbolic geometry).

Edit: well, it is a example were the sets where expected to be the same, so (2) fails, so perhaps I should delete this as answer and post as comment.

Edit$^2$: To formally have (2) consider "absolute geometry" (expected to be euclidean) and "hyperbolic geometry" (expected to be inconsistent). They were in fact different, but for reasons quite different from the expected ones.

Edit$^3$: in the same vein, "geometric problems solvable by ruler and compass alone" and other kinds of problems (in Pappus' classification, "plane" vs. "solid" vs. "linear").

Answer 3

The large cardinal hierarchy in set theory can be seen as an example of the phenomenon. There seems to be little reason initially to have expected that questions about what kinds of infinite sets exist would have such a fundamentally different meta-mathematical character than other ordinary questions in mathematics. Surely it would have seemed reasonable, for example, to expect to settle such questions either by proving the existence claims or refuting them, and there were many detailed questions about large cardinals from the early days. I imagine that in the early days, the various large cardinals were perhaps clumped together in a few groups. For example, it wasn't understood until much later than you would expect how the measurable cardinals related to the inaccessible cardinals. Meanwhile, now, it turns out not only that the independence phenomenon runs completely through the hierarchy, but worse, we cannot settle the independence of the existence of large cardinals even by means of the type of relative consistency results found with the continuum hypothesis and the axiom of choice. This is because the hierarchy is not merely increasing in deductive strength but also in consistency strength. So the large cardinal hierarchy turns out to instantiate the consistency strength hierarchy predicted by Gödel's incompleteness theorem. Furthermore, it does so not with weird self-referential assertions or purely syntactic consistency assertions, of the kind appearing in the proof of the incompleteness theorem, but, rather, with highly natural assertions about infinite combinatorics, assertions which answer natural questions that had arisen independently. The final resolution is that this tower appears to be taller than we can imagine, and very finely separated into levels, each of which reflects important parts of its nature to lower levels, a skyscraper fractal.

Answer 4

a nice historical & possibly relevant analogy of P vs NP in mathematics (other than the parallel geometry postulate already cited) is the impossibility of "squaring the circle". the problem is simply stated and naturally conjectured. for literally roughly two millenia (this problem dates to the Greeks) many amateur "experimentalists" attempted to find constructions where they could square the circle or trisect an angle and there were many faulty proof claims, some involving many steps [and were hard to refute even by experts who spent significant time].

the problem was proven impossible in 1882 by Lindemann's proof of the transcendence of Pi. the proof was extremely complex at the time and took dozens of pages.

so a simply-stated mathematical question/fact about the classification of an extremely fundamental mathematical constant, which related to basic constructions in geometry, required a very difficult solution spanning many centuries of analysis.

so the modern equivalent/phenomenon of finding P=NP algorithms/proofs may be similar in ways to this ancient question if it is ever proven that P≠NP. one also would reasonably expect/presume that a P≠NP proof will be very complex and require many pages by an expert. here the amateur geometers with their circle squaring proofs are analogous to amateur programmers who think they have P-time algorithms for NP complete problems.

it is timeconsuming even for experts to refute these claims and most experts adamantly refuse to participate in that exercise. also if P≠NP then that can never be demonstrated by finding an algorithm, it seems to fundamentally require a proof construction by a mathematician and not code written by a programmer (and despite the Curry-Howard correspondence there are key differences there).

Answer 5

LESSONS FROM CRYSTALLOGRAPHIC CLASSIFICATION

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

The Crystallographic Classification Problem  In two and three dimensions, separate the set of ordered materials (that exhibit discrete Fourier diffraction patterns) from the set of disordered materials (that don't), and comprehensively classify the ordered materials on the basis of their Fourier diffraction patterns.

The Relevance to the Question Asked  We imagine that "an invisible fence" separates ordered materials from disordered materials. Viewed as a problem in tiling, we appreciate that abstract tile-sets and physical crystals alike are richly endowed with various (tricky!) reductions, as stipulated in the question-asked.

Historical Provenance For centuries mathematicians believed that the 230 crystallographic space groups rigorously and exhaustively classified the separation of crystallographically ordered from disordered materials... until the unexpected experimental observation of quasicrystals forced radical amendments to the mathematical postulates associated to the classification problem.

The Resolution 

• Raphael Robinson's canonical "Undecidability and nonperiodicity for tilings of the plane" (1971) established that the prediction of crystal diffraction patterns is undecidable in both mathematical senses of "undecidable": first, the decision function associated to tile-set classification is not Turing-computable; second, given an axiom system at least as strong as PA, tile-sets exist for which the existence of periodic 2D tilings---and thus discrete Fourier diffraction patterns---is neither provable nor refutable in that system.

• Dan Schectman's quasicrystal discovery mandated formal extensions to the traditional postulates of crystallography.

• In retrospect, the infamously rancorous opposition to (now-Nobelist) Dan Schectman's extended crystallographic classification framework---e.g., Linus Pauling's sardonic yet mathematically ill-grounded assertion "There is no such thing as quasicrystals, only quasi-scientists"---contributed insubstantially to progress in the classification problem

Conclusion The Crystallographic Classification Problem teaches plainly that long-accepted mathematical postulates sometimes require radical reconsideration, and teaches too that sardonic rancor contributes little to mathematical discourse.

Answer 6

I will just clarify Shelah's result. I am not sure that it really corresponds to the original issue. Morley conjectured in the 1960's that the number of models (up to isomorphism) of a complete first order theory with cardinal $\kappa$, should be increasing in $\kappa$ (with the one known exception of the theories such as algebraically closed fields which have countably many countable models and one in all larger cardinalities).

Shelah's remarkable strategy for answer this was to conjecture around 1970 all possible spectrum functions - a short list but with parameters. Later in the 70's he showed this was 'eventually correct'. Work of Hart, Hrushovski, and Laskowski cleaned up the smaller cardinals. The idea of the argument is to show that either a theory has a property which implies the maximal number of models or else the failure of this condition takes one toward assigning invariants. (e.g. unstable - there is a formula $\phi(\bar{x},\bar{y})$ and a sequence $\bar{a}_i, \bar{b}_i$ such that $\phi(\bar{a}_i, \bar{b}_j)$ iff $i < j$ - this is called the order property; well order does not arise here.) A collection of 5 such dichotomies leads one to classifiable theories; every model is determined by a 'cardinal invariant' and so the number of models in $\kappa$ is bounded well-below $2^\kappa$.

Answer 7

A couple of other answers have mentioned Shelah and cardinal invariants, but not the following famous result that IMO is a pretty good answer to Scott's question.

Theorem (Malliaris–Shelah). $\mathfrak p = \mathfrak t$.

The precise meaning of this theorem requires quite a few definitions; instead of reviewing them here, I refer the reader to Soukup's expository article or Gowers's blog. But roughly speaking, the picture is this: set theorists have defined over a dozen "cardinal invariants" (of which $\mathfrak p$ and $\mathfrak t$ are examples) that lie non-strictly between $\aleph_0$ (the cardinality of the integers) and $2^{\aleph_0}$ (the cardinality of the continuum).

The rule of thumb is that any hypothesized relationship between such cardinal invariants (e.g., that they are equal, or that one is less than the other) is either easy to prove, or independent of ZFC. Often one can find models that realize several hypothesized relationships simultaneously. In a sense, the situation is reminiscent of oracle separations in computational complexity theory.

In the case of $\mathfrak p$ and $\mathfrak t$, it is easy to prove that $\mathfrak p \le \mathfrak t$. On the other hand, there is no easy proof of either $\mathfrak p = \mathfrak t$ or $\mathfrak p < \mathfrak t$, and it was widely believed that $\mathfrak p = \mathfrak t$ was independent of ZFC. Certainly equalities such as $\mathfrak p = \aleph_1$ or $\mathfrak p = \aleph_2$ are independent of ZFC. Therefore it was a great surprise when Malliaris and Shelah showed that $\mathfrak p = \mathfrak t$ is a theorem of ZFC.

I don't know if there was a perceived "invisible fence" prior to Malliaris and Shelah's result. I suppose that if one wants to push the analogy between oracle results in complexity theory and independence results in set theory, one could say that people were able to find "oracles" that collapsed the two but were unable to find "oracles" that separated the two, so this might suggest that one should have "expected" $\mathfrak p = \mathfrak t$. But the analogy doesn't quite work because in the set-theoretic case, "relativizing both ways" actually resolves the problem outright, by showing that the statement is independent of ZFC.

Answer 8

I have been intrigued by results of Shelah's classification theory. My interpretation of the situation is as follows ( it is full of simplifications, nonstandard terminology, and likely technical error; I welcome correction or a similar and more accurate interpretation): Given a complete theory T in a countable language L (so any L-sentence $\phi$ or its negation belong to T), we want to determine $\kappa=I(T,\lambda)$, the cardinality of the set of isomorphism types of L-structures which have an underlying set of size $\lambda$ and are models of the theory T. What properties of T can determine the value of $\kappa$?

Shelah finds that for many cases, the number of models is the maximum possible ($2^\lambda$) and that there are not many possibilities otherwise. He gives conditions for theories such as stable, superstable, and others which will (with other conditions) imply that there are fewer models (in fact, not many possibilities for $I(T, \lambda)$ as a function of $\lambda$). One of the conditions is (similar to the idea) that a well order is definable within the theory, and there are other conditions regarding definability within the theory.

When one is able to define such concepts within the theory, one can find more structure and determine limitations for the kinds of and number of models. I have always thought that greedy algorithms and other polynomial time solutions to certain problems were like these theories in which some structure was definable and that allowed for quick solutions (few models), and that other problems that did not have quick solutions could not because there was insufficient structure in the problem to find such a solution (too many models/possibilities to check).

When I have finished some other projects, I may return to this and draw a tighter analogy.

Gerhard "Wants Quick Solutions To Projects" Paseman, 2014.03.13

Answer 9

The OP's question seems to be equivalent to "what are some of the influential dichotomies in mathematics?" If that's the question, I would cite a result that has attracted a lot of attention over the past few decades, such as Gromov's theorem that groups of polynomial growth are (nearly) nilpotent. This one has the advantage of sharing the word "polynomial" with the OP's question.

Answer 10

LESSONS FROM RUNTIME CLASSIFICATION

Edits  The nomenclature of the original answer have been amended to parallel the (higher-rated) "Lessons from crystallographic classification;" on the grounds that both classification problems---crystallographic and runtime---are eminently practical, such that both problems were studied by engineers and scientists long before mathematicians.

These two problems are similar too in their various overlaps and natural affinities with respect to PvsNP (as the answers summarize). Henry Cohn's thoughtful remarks helped me to appreciate these parallels.

It is plausible that the (seemingly complete) present-day resolution of the crystallographic classification problem, and the present-day partial resolution of the runtime classification problem, both may foreshadow elements of an eventual resolution of the PvsNP problem. Needless to say, it is neither necessary, nor feasible, nor even desirable, that everyone think alike in this regard.

---

The Question Asked

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

The Runtime Classification Problem for TMs  Given a Turing Machine (TM) promised to be in P, and a non-negative real runtime exponent $k$, a commonplace and eminently practical math-and-engineering question is this: "Is the TM's runtime $O(n^k)$ with respect to input length $n$?"

We call this is the Runtime Classification Problem for TMs.

The Relevance to the Question Asked  We imagine that "an invisible fence" separates TMs whose runtimes are slower-than-$n^k$ from TMs whose runtimes are $n^k$-or-faster, and we are asked to decide whether a given TM resides on one side or the other.

Historical Provenance (per Henry Cohn's comment)  In the decades prior to WWII, the engineering question "What maximal accuracy is compatible with real-time computation of firing solutions?" was pragmatically answered by computational devices such as the (then-secret) Mark 1 Fire Control Computer, and was fictionally addressed in charming stories such as E. E. "Doc" Smith's The Vortex Blaster.

This same provenance is naturally framed in the terms of the question-asked as " Mathematicians  engineers conjectured that the two classes [of real-time versus too-slow computation processes] were unequal, but were unable to prove or disprove that for a long time."

The Resolution  Emanuele Viola has proved that the Runtime Classification Problem for TMs is undecidable.

So in regard to runtime exponents, the "invisible fence" turns out to be formally invisible.

Present Practice  The formal invisibility of the Runtime Fence provides scant grounds to expect that efficient, reliable, real-time computation processes---error-correction by solving NP-complete belief-propagation problems, for example---can be designed at all. And yet for reasons that remain poorly understood by engineers and mathematicians, real-time processes that solve NP-complete problems commonly are designed rationally and perform near-optimally.

NATURAL EXTENSIONS

The Runtime Classification Problem for Languages    Given a language L, the Runtime Classification Problem can be posed for the most efficient TM that recognizes that language. We call this The Runtime Classification Problem for Languages.

The Resolution  The Runtime Classification Problem for Languages is natural, open, apparently difficult, and conjecturally undecidable.

For definitional details, comments, and mathematical history, see the TCS StackExchange community wiki "Does P contain languages whose existence is independent of PA or ZFC?."