{\huge In Praise Of P=NP Proofs}

\vspace{.2in} Why they can be important

Joe Bloggs is not a computer scientist, at least not one that we know. As noted by Wikipedia, Joe Bloggs is a ``placeholder name'' like ``John Doe'' or ``Jane Roe'' in the US, or ``Ashok Kumar'' in India. Sometimes real people have or acquire the placeholder names: Ashok Kumar (born Kumudlal Ganguly) was a famous actor in India, whose acting brothers also took the surname ``Kumar,'' and the ``Roe'' in Roe v. Wade is Norma McCorvey. We especially like the fact that ``Joe Bloggs'' came about long before there were blogs. A public restraining order is indeed called an ``Ashok Kumar order'' in India the way it is called a ``John Doe order'' in the US.

Today Ken and I consider whether there should be a ``John Doe order'' against submitting claimed proofs of $latex {\mathsf{P = NP}}&fg=000000$ or $latex {\mathsf{P \neq NP}}&fg=000000$, and instead point out some reasons that we should look at such attempts by Ashok, Jane, or Joe.

I know this is at variance with the general attitude that such proofs must be wrong, and looking at them is a complete waste of time. I would like to explain why this is not the case. Ken and I have spent a good deal of time looking at such proofs---they do come in at the yearly rate suggested by Gerhard Woeginger's P-versus-NP page While there are attempts and there are attempts, we think that subject to minimal criteria, it is fruitful to look at them.

Let's explain why.

Reason I

The proof could be correct. We have discussed many times before that in mathematics people often had valid proofs that were at first rejected. Often they were only later found to be correct after another more mainstream proof was discovered. One of my favorite examples is the proof by Kurt Heegner of the beautiful theorem:

Theorem 1 Let $latex {K}&fg=000000$ be an imaginary quadratic field whose ring of integers has class number one. Then $latex {K}&fg=000000$ is $latex {\mathbb{Q}(\sqrt{-X})}&fg=000000$ where $latex {X}&fg=000000$ is one of
$latex \displaystyle 1,2,3,7,11,19,43,67,163. &fg=000000$

Recall class number one means that the ideals have unique factorization.

Heegner was a radio engineer and published his ``proof'' in 1952. Few believed it. In 1969 the the eminent number theorist Harold Stark solved the problem. To his great credit he went back and re-read Heegner's proof and realized it was essentially the same as his. It had some minor errors that were easily fixed. See this exposition by Jeremy Booher for more details.

This speaks however the first minimal requirement: The proof should have a short ``elevator pitch'' as to why it can be correct, quite apart from saying to read the details. What is the new idea that others have not seen or appreciated, and how is it used in the proof? How can it surmount known barriers to the conclusion? This needs to be stated up-front.

Reason II

The proof could be wrong, but $latex {\dots}&fg=000000$ Part of our view at GLL is that we are here to help spread the word about theory and mathematics. We do not guarentee that we will look at every attempt, so do not flood us with them. But we have seen some interesting ideas raised by some of the attempts. My favorite ones that I am unable to completely understand are those that try to use physical arguments to show that if $latex {\mathsf{P=NP}}&fg=000000$, then there would be some strange physical consequence.

This speaks to the issue of distinguishing ``true efficiency'' from ``galactic algorithms'' which while technically polynomial have running times like $latex {n^{100}}&fg=000000$. Or $latex {n^{10,000}}&fg=000000$, an exponent seriously mentioned to us in correspondence this year. Thus a second minimal requirement for those on the ``equal'' side is to state the algorithm and estimate its running time. The algorithm may depend on ``nonconstructive'' features---as we have covered---but it should always be possible to state it once those features are itemized. Even for the ``not equal'' side, with some of the physics-based papers this distinction is not clear.

Reason III

The proof could be wrong, but interesting. The most important reason I believe is that failed proofs have in a number of cases helped create new mathematics. The best example of this is probably the work on extended formulation of polytopes. This notion was created by Mihalis Yannakakis in an attempt to show that a whole class of proof structures for $latex {\mathsf{P=NP}}&fg=000000$ must fail.

Yannakakis was motivated by the 1986-1987 attempted proofs that $latex {\mathsf{P=NP}}&fg=000000$ of Ted Swart. He tried to give linear programming formulations of polynomial size for the Hamiltonian cycle problem. This would have proved that $latex {\mathsf{P=NP}}&fg=000000$ since linear programming is in $latex {\mathsf{P}}&fg=000000$ and the Hamiltonian cycle problem is $latex {\mathsf{NP}}&fg=000000$-hard. Yannakakis showed that Swart's approach was doomed because it created a kind of symmetric extended formulation of the feasibility polytopes $latex {X}&fg=000000$ for the standard formulation of the Traveling Salesman problem. He proved that all such symmetric extensions of $latex {X}&fg=000000$ must have exponentially many constraints, thus ruling out the programs Swart was trying to create.

I am sure that Swart was greatly disappointed that he did not solve $latex {\mathsf{P=NP}}&fg=000000$. And I doubt he would be happy to see that his work helped create the entire field of extended formulations, but his work did just that. Without Swart would we have seen this work done? Would it have been created anyway eventually, or would we be living in a world without extended formulation theorems? I would assert that at a minimum the creation of this area would have taken many more years to be created, if at all. Thanks Ted.

Yannakakis's work has in this decade been actively pursued by Sebastian Pokutta and his colleagues. They began by removing the ``symmetric'' condition on the kind of formulations ruled out, and then liberalized the kinds of extensions. Their work has greatly extended the range of ``no-go'' theorems, but quite apart from this negative purpose, has created a lot of beautiful mathematics. Moreover their work links several areas: it began with some new thoughts in quantum communication complexity, and has greatly increased our understanding of the structure of polytopes. Ken and I have still been struggling with its exact reach.

Thus our third minimal requirement is that the proof should engage neighboring areas of theory. As we have said before, this should include deriving some lesser consequences, short of shooting the moon. If you've proved ``equal,'' is it easier to see why factoring has a sub-exponential time algorithm? If ``not equal,'' can you say why $latex {\mathsf{3SAT}}&fg=000000$ does not have a linear time algorithm? And why must the first blush be separating $latex {\mathsf{NP}}&fg=000000$ rather than $latex {\mathsf{PSPACE}}&fg=000000$ from $latex {\mathsf{P}}&fg=000000$. If either side, what about the mechanics of separating $latex {\mathsf{NEXP}}&fg=000000$ from $latex {\mathsf{BPP}}&fg=000000$ or $latex {\mathsf{EXP}}&fg=000000$ from $latex {\mathsf{ZPP}}&fg=000000$? These are addressed in a recent paper by Harry Buhrman and friends and a survey by Ryan Williams, both of which we aim to cover when time allows.

Open Problems

What do you think? Is there a possible proof out there that we will avoid reading that is correct, or useful, or contains some interesting new ideas?

\documentclass[14pt]{article}

\usepackage{epsf} \usepackage{epsfig} \usepackage{color}

\usepackage{graphicx} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{wrapfig} \usepackage{subfigure} \usepackage{hyperref}

\setlength{\parindent}{0pt} \setlength{\parskip}{1ex} \widowpenalty 10000

\usepackage{color} \definecolor{MyDarkBlue}{rgb}{0.1,0,0.9} \newcommand{\aside}[1]{\textcolor{MyDarkBlue}{#1}}

\usepackage{enumerate}

\usepackage{lineno} \newcommand{\mybox}[1] {

{\small \framebox[3in]{ {4.5in} {\sf #1} } }

}

\newtheorem{theorem}{Theorem}[section] \newtheorem{definition}[theorem]{Definition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \documentclass[14pt]{article}