Is the end of the world uncomfortably close?

src

Derek de Solla Price created scientometrics, which is “the science of measuring and analyzing science.” You can tell you’re a natural theoretician if you instantly think, what happens when scientometrics is applied to itself? But there is no paradox of self-reference here, because scientometrics per se is applied to the science of the past, to papers that have already been published. Yet we who are doing science have to look ahead to impact on the future, and that involves unpublished possibilities.

Today Ken and I want to discuss what keeps us worried sometimes.

David Hilbert once said:

One can measure the importance of a scientific work by the number of earlier publications rendered superfluous by it.

Our worry looking ahead is based exactly on this quotation. Some conjectures are what we will call “normal” and others are “abnormal.” A normal conjecture is one whose truth does not wipe out previous developments. For example, in our opinion Andrew Wiles’ two papers proving Fermat’s Last Theorem, one joint with Richard Taylor, did not diminish most previous work—indeed they built on it. A grand conjecture like the Langlands Program would validate our understanding of algebra and lash previous work together into a new foundation. But abnormal results do more than overshadow past work.

P and NP: Equal or Not Equal?

Right now the P versus NP page lists one dozen claimed proofs of since January 2011, and one dozen claimed proofs of over the same time. Many of the 70 previously-claimed proofs are still circulating. Some are easily seen to be incorrect, while others are less easily dismissed.

Many of our colleagues believe that a proof of is unlikely for two reasons. First, they believe that ; second, they believe a proof that they are equal, if correct, would be very difficult. So difficult that no one will find it for years, decades, or perhaps forever.

I (Dick) believe that is a possible outcome. I have explained many times here that this need not mean that there is a practical algorithm for , but there could be a polynomial-time algorithm.

Jin-Yi Cai, who has been a faculty colleague of both Ken and myself, is visiting Buffalo this weekend, and gives permission to relay his main reason for believing , though it doesn’t quite extend to itself. Counting problems seem to yield especially notable examples where the general problem is -complete but a natural special case has a polynomial-time algorithm. Consider, for example, the FKT algorithm for counting perfect matchings in graphs that are planar, which is a foundation for incredibly deep and sweeping dichotomies (see Jin-Yi’s own site for papers) showing every problem in the class is either in or -hard with nothing in-between. The reductions are usually based on algebraic methods such as eigenvalues and eigenvectors, which have no direct relation with the polynomial time algorithms; but they always manage to miraculously avoid hitting the domains of these algorithms, while sweeping everything else. If were equal to , the reductions would have no extrinsic reason to avoid hitting planar graphs and others that fall into the deep tractable cases. The fact of seems required to explain such serendipitous avoidance of deep cases.

Normal Conjectures

Right now in mathematics there is the potential proof solving one of the great open problems of number theory. This is the ABC Conjecture which we discussed here. Besides the length and complexity of this proof whether correct or not it appears to have substantial new mathematics. The biggest surprise with this new proof is that while many have believed all along that the ABC Conjecture is true, no one seemed to have any approach at all. Of course the proof could be wrong, could have a bug, yet it may also be correct. We will see.

The Riemann Hypothesis is a long-standing conjecture with deep impact. Although we may expect that a proof would carry foundational new insights, the fact of its truth would ratify beliefs we are already building on. The falseness of Riemann [in any of various forms] would certainly wipe out many papers with theorems that begin “Assuming the [extended] Riemann Hypothesis…”—as Lance Fortnow just now listed among “Things a Complexity Theorist Should Do At Least Once.”

However, Riemann can be viewed as part of a spectrum of assertions about the distribution of primes and the behavior of the Möbius function. Cramér’s conjecture, as we discussed here, makes a much stronger assertion about gaps between primes than what follows directly from Riemann, versus for various . We can compare the consequences of Riemann being false with those of Cramér’s and/or some other stronger statements being false while Riemann is true. That we would feel no apocalypse in the latter case hints that number theory could move on without Riemann with much intact. Some desired properties need only a weaker hypothesis, and the Prime Number Theorem, which has many current applications including Borsuk’s problem which we just discussed, does not need it at all.

There is a difference between “normal” conjectures like the ABC Conjecture and our own . If yes, if it is true, then the world of complexity theory is altered forever. A huge part of computational complexity theory disappears.

Abnormal Conjectures

To see why is special, let us assume for a moment that someone proves that expected result that . This would be great, would win awards, a million dollars, and have terrific impact. However, it would not change the world as we know it. It would confirm what most of the community believes is true.

Imagine, if you can, that someone proves the unexpected: they prove . Perhaps it is a real algorithm that can be run, or perhaps it is a galactic algorithm that cannot. In either case it would cause a rip—not just a ripple—through theory that would be stunning.

Much of CS theory would disappear. In my own research some of Ken’s and my “best” results would survive, but many would be destroyed. The Karp-Lipton Theorem is gone in this world. Ditto all “dichotomy” results between and -complete, and for , Jin-Yi’s similar work. Many barrier results, such as oracle theorems and natural proofs, lose their main motivation, while much fine structure in hardness-versus-randomness tradeoffs would be blown up. The PCP Theorem and all the related work is gone. Modern cryptography could survive if the the algorithm were galactic, but otherwise would be in trouble.

I am currently teaching Complexity Theory at Tech using the textbook by Sanjeev Arora and Boaz Barak, while Ken is using the new edition of the text by Steve Homer and Alan Selman, supplemented by his CRC Handbook chapters with Eric Allender and Michael Loui. Most of the 573 pages of Arora-Barak would be gone:

• Delete all of chapter 3 on .
• Delete all of chapter 5 on the polynomial hierarchy.
• Delete most of chapter 6 on circuits.
• Delete all of chapter 7 on probabilistic computation.
• Mark as dangerous chapter 9 on cryptography.
• Delete most of chapter 10 on quantum computation—who would care about Shor’s algorithm then?
• Delete all of chapter 11 on the PCP theorem.

I will stop here. Most of the initial part of the book is gone. The same for much of Homer-Selman, and basically all of the “Reducibility and Completensss” CRC chapter.

Open Problems

Is the wanton conceptual destruction wrought by , or even more by or , a material reason to believe their opposites? How does it compare with Jin-Yi Cai’s reason?

Would it be a true apocalypse, or would we move to talking about “nearly-linear” versus “quadratic-plus” time, starting (say) with Merkle’s Puzzles?

[updated paragraph on Jin-Yi’s work]