[FOM] P NP buzz
Harvey Friedman
friedman at math.ohio-state.edu
Sun Aug 15 13:50:24 EDT 2010
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.
More information about the FOM
mailing list