A meta-note about NP-completeness and its current state of (lack of) knowledge of

Recently, Scott Aaronson wrote a short-book-length summary of the current state of knowledge about NP-completeness. This is an honorable tradition, starting with the classic and definitive book by Garey and Johnson, then Sipser, Cook, Wigderson, and Allender. Aaronson gives his spin on things (a little more on the quantum computing side) but hits well (like the others) all the great points: Turing Machines, reductions, completeness, the hierarchy of harder problems, what is conjectured to be the case (P != NP), etc.

What I want to do is point out the unsaid things, those things that are obvious to insiders and don't need to be said, but are inscrutable to outsiders. The outsider may realize it or be told it explicitly but not really get it understand it because, you know, math.

The most important thing is that, of all the things stated, all the theorems, all the papers and books, the great number of words and symbols written about the subject, all these things are written about what we don't know about NP-completeness. We don't know whether P = NP. We don't know whether NP = coNP. We don't even know whether Graph Isomorphism is in P (early 2017 Babai retracted 2015 quasi-polytime algorithm, just sub-exponential). We don't know. We don't know so much. Every day there are books and papers published that are essentially just outlining the boundaries of all the so many things we don't know about P vs NP.

Most of the theory surrounding P vs NP was developed in the 1970's. Lots of small results (with great effort!) have been established over the years. We do know now that NP = PCP(log n,1) (Arora et al. 1998), NEXP is not in ACC^0 (Williams 2011). No, not small results but proofs of things that we really expected to be easy. Some specific problems have been shown to be in a particular class unknown before: Primality is in P (AKS 2004),  LinProg is in P (Karmarkar 1986)  UGraph Reachability is in L (Reingold 2004), but one usually expects it (relatively) easy to find an optimal algorithm for a problem...it just  turns out that all these were very difficult to discover.

But all these are minor results. One-offs. They may spark a cottage industry in their subcommunity and are undeniably important. But they are... they are only making infinitesimal progress towards P vs NP. In fact, because of this meta-intractability (get it? the problem of intractability is itself intractable), no one actually is currently attacking the direct problem of P vs NP. Most of the (great amount of) work goes into ancillary situations, extending minor results, changing the problem, all in the hopes that there might uncover one little tiny bit that makes the difference. It feels like panning for gold in that you dig up tons and toms of material, wash it through multiple levels of gratings, wash it some more, refine the dirt, wash the dirt some more, and if you get a couple of tiny specks of non-dirt that just turns out to be copper, you call that a good day.

As far as history of science goes, this is a rare situation. Usually, a bunch of data is collected, some patterns are noticed, you collect a lot more data (and all this new data is useful and interesting), these patterns look like they repeat in different weird ways, then a consolidating theory (a scientific experiential theory that is) is formulated that generalizes and explains the prior data, and then a search is made for even more data which then either confirms the theory or encourages refinement or maybe even over-throw of the first theory. Similarly in math (which the P vs NP problem is a part of), a bunch of small theorems are proven, then some (usually a group but usually a single person gets good press) see a pattern, add a few definitions and prove a big theorem that combines them all, and then further consequences of that big theory are applied to more instances (note that yes, in math it is very rare (never?) for a big theory to be overthrown because a proof is a proof (right?) of course it is, but the refinement comes either in how many new more complicated problems to explore are created that go beyond the first theory.

Anyway, the rare situation with P vs NP is that we've essentially gone almost 40 years now with the same state of affairs of lack of knowledge. The progress that there is is not steady, and any gains seem underwhelming at least from the outside (the first outsider thought is "You're so smart, shouldn't you have figured that out a long time ago?"). Even the most minor seeming result is astounding (NEXP is a very intractable class and ACC^0 a very tractable one - how come it was so hard to show NEXP not in ACC^0?).

Also, back to more basic things. All this literature, all this theorem proving hasn't really established, hasn't really given a definitive proof of the pinnacle question P vs NP...but it's almost a scientific proof, a proof by having lots of examples in mostly one direction. All the reductions, all the intermediate problems, al the proofs of no proof by method X, are really supporting evidence (not mathematical definitude) just supporting the particular direction that P is a strict, proper, much smaller subset of NP, that NP problems are actually harder and we really can't find exact and fast algorithms for NP-complete problems. That is, even though we have 40 years of not proving one way or the other, it (almost) all goes in the direction that they're probably not the same.