[FOM] P NP buzz

[Harvey Friedman]

Here is an update of my corner of the Lipton blog on this "proof" of  
P != NP. See http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

It is my impression that the papers I was referred to concern only  
what happens if P = NP is proved in weak systems, which is at cross  
purposes with what I was talking about.

Specifically, it is my impression that nothing is known about the rate  
of growth of P = NP put in Pi-0-2 (I.e., AE) form.

Readers, please correct me if I am wrong about this. I wrote most of  
these postings while I was asleep.

Barkley Rosser is the son of the greatly famous Barkley Rosser.

Harvey Friedman

Harvey Friedman PERMALINK
August 14, 2010 10:10 am
Response to T.
I like your point that I may be calling for , as you say, “heightened  
standards or articulation of standards so as to prevent irregular  
proofs from capturing researcher-time on a large scale”, where, as  
you suggest, this may happen extremely rarely. But perhaps there are  
enough famous open problems left in mathematics and mathematical  
computer science, so that this kind of reform would have greater  
applicability? Also, and most importantly, the kind of educational  
reform I proposed could really help in those much more common  
situations of people submitting papers for publication – or even  
internet publication – with erroneous proofs. I’m thinking that it  
would not only ease the burden on Journals, but also help unfortunate  
authors. What remains to be seen is whether this reform can really  
made sufficiently user friendly. I think it can, with the right kind  
of “logic engineering”. Perhaps we (or I) need to know more about  
what causes intelligent people to cling to erroneous mathematical  
arguments? I do think that unfamiliarity with what it would even look  
like to get to the “absolute bottom” of something, plays a big  
role. As a logician, I am more familiar with “absolute bottoms”  
than most mathematical people.

Barkley Rosser PERMALINK

August 14, 2010 1:33 am
This will not be well received, and my late father would not approve  
(even if his old friend Steve Kleene would probably chuckle a bit),  
but I think it should just be put out there for the record. This  
“proof” is fundamentally non-constructive. As it is, it appears not  
to be correct anyway for reasons that Neil Immermann and various  
others have pointed out. But, even if their issues were somehow to be  
overcome, there would remain doubt from the point of view of a deeper  
critique.

For the record, I have always found proofs by contradiction to be  
elegant and beautiful, even as I am unfortunately aware of their  
ultimate limitations.

REPLY

Harvey Friedman PERMALINK
August 14, 2010 5:37 am
There are some powerful automatic conversion theorems in mathematical  
logic to the effect that if a sentence of a certain form is provable  
in the usual sense then it is provable constructively. Of course,  
these terms need to be defined for the purpose of this family of  
theorems. Generally speaking, this family of general results takes the  
following form, for a large variety of axiom systems T. Let T- be the  
constructive (intuitonistic) form of T, where we simply require that  
the proofs avoid the law of excluded middle (in the usual sense as  
formulated by Arend Heyting). It is known that under general  
conditions on T, any AE sentence provable in T is already provable in  
T-, and there is an explicit conversion method for this, known as the  
A-translation. Here AE means (for all integers n)(there exists integer  
m) such that something readily testable holds.

The most commonly quoted case of this is where T = Peano Arithmetic =  
PA, and T- = Heyting Arithmetic = HA. HA is the constructive form of  
PA. But the result applies flexibly to many other systems, both much  
stronger and much weaker than Peano Arithmetic/Heyting Arithmetic.

The statement P = NP takes the form EA, which means (numerical)  
existential universal, using SAT. So P !NP takes the form not(EA).  
This conversion theory tells us how to convert a proof of not(EA) in  
PA to a proof of not(EA) in HA, and more. Write P != NP in the form  
(En)(Am)(P(n,m)), where P is totally innocent logically. Here “E”  
is “exists”, and “A” is “for all”.

If PA proves not(En)(Am)(P(n,m)), then HA proves not only not(En)(Am) 
(P(n,m)), but even (An)(Em)(not P(n,m)), and the conversion from PA  
proof to HA proof is rather explicit, using the A-translation.

Returning to the specific case at hand, of P != NP, these  
considerations tell us, for example, that any (CORRECT!) proof in PA  
of P !=NP can be explicitly converted to a proof in HA of P !=NP. In  
fact, it can be converted to a proof in HA of the statement T(f) =

“for all constants c, any algorithm of size at most n with built in  
running time <= (x+c)^c must give the wrong answer to SAT at some  
input of size x <= f(n,c)"

where f is a so called <epsilon_0 recursive function. I am under the  
impression in this Deololikar P !=NP "proof", this statement above  
under quote signs is "proved" where f is an exponential(?).

BTW, this raises some interesting questions that perhaps have been  
addressed(?) independently of any logical issues. What can we say  
about the statement T(f) when f is slow growing? I.e., what is the  
"strongest" statement that we can hope to prove, or at least can't  
refute, or believe, concerning the identification of, or size of, a  
mistake that any purported algorithm for SAT of a certain size running  
in a certain time must make? This question can obviously be raised in  
a very wide range of complexity contexts, and surely(?) has been  
addressed.

REPLY
		
Kenneth W. Regan PERMALINK
August 14, 2010 8:48 am
For fast-growing f this was addressed by many people (including  
DeMillo-Lipton); then Deborah Joseph and Paul Young argued in the  
early 1980′s that f should be no worse than elementary. The latest  
effort in this line that I’ve tracked is by Shai Ben-David and Shai  
Halevi (ps.gz here). But all this stops short of a really concrete  
treatment of SAT, and maybe now that should be revisited. Scott  
Aaronson’s 2003 surveyhttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.65 
48 has more.

Minor typo in paragraph beginning “The statement P=NP…”, should  
say later “Write P != NP in the form not(En)(Am)(P(n,m))” (missing  
“not”).

Harvey Friedman PERMALINK
August 14, 2010 9:45 am
I took a quick glance at the references you mention (Kenneth W.  
Regan), and these “arguments” seem to be exploiting the observation  
that current concrete independence results are connected with fast  
growing functions – e.g., no current concrete independence results  
for Pi-0-1 (purely universal sentences quantifying over integers).

This is no longer the case. See the latest,http://www.cs.nyu.edu/pipermail/fom/2010-August/014972.html 
  where natural (steadily increasingly natural) Pi-0-1 sentences are  
claimed to have been proved independent of ZFC (not just PA), and in  
fact stronger systems involving large cardinals. Here natural Pi-0-1  
sentences (i.e., A sentences) relate to kernels in order invariant  
digraphs on the rationals.

In any case, I didn’t spot an outright definite claim that, e.g., if  
P != NP is true in Pi-0-2 (i.e., AE) form, then it is true iterated  
exponentially. Did I misread these papers, and they do claim such a  
thing? (I’m better at thinking than reading – sometimes this is a  
handicap).

Kenneth W. Regan PERMALINK
August 14, 2010 10:14 am
Here is a TR version of the paper “Polynomial Time Computations in  
Models of ET” by Deborah Joseph—its essence is also mentioned in  
other papers by Joseph and (Paul) Young which can be found online.  
Maybe it speaks toward what your reference says about towers. (A  
slightly longer reply with 2 links got into the mod queue; I see that  
didn’t happen to my first reply because I muffed the Ben-David-Halevi  
link.)

Barkley Rosser PERMALINK
August 14, 2010 12:00 pm
Thank you Harvey and others. Very useful.