Hauptmann P≠NP attack via polynomial hierarchy noncollapse

5 Replies

hi all. low-quality P vs NP “proofs” are a dime-a-dozen and scatter/ “litter” arxiv like dandelions in the grass. however, occasionally ostensibly “high quality” appearing proofs show up. that is the recent case with Hauptmann.[7]

do not want to write a lot on this subject, because have been somewhat “burned” in the past on it. but this is not an uncommon experience/ case for anyone who spends much time with these proofs (as if there is something “typical” about them, and yet history shows there is, which is both judgemental and paradoxical).

the proof is notable though, represents major effort/ background knowledge, and deserves mention. it has been around since february and a recent revision caught the eye of reddit where there is some reaction.[1] usually hear about stuff like this earlier, scan new CS titles on arxiv nearly daily, but missed it myself, maybe partly due to the authors title/ abstract style (see below). Hauptmann has great credentials; Phd and is professor at university of Bonn.[2] CS “near-janitor” Woeginger seems to have been aware of it for a few months.[3]

we had some discussion in the theory salon chat room.[6] as someone remarked there, the proof passes Aaronsons “quality” criteria for a non-crank proof which he posted soon after the deolalikar attempt roughly now ~½ decade ago.[4]

what is not well known about the deolalikar attempt that went quasi-viral in academic circles is that (only discovered this by extensive googling myself) Cook halfway endorsed it in email to colleagues. maybe partly because it used descriptive complexity techniques, something Cook specializes in.

this latest attempt seems to me to cite many very/ highly relevant papers that have run across and cited (in this blog & stackexchange writing etc) in my own long meanderings on the subject (now close to ~2½ decade). that is just a circumstantial element of course. nevertheless overall the intellectual engagement with the subject is far higher than a garden-variety crank proof.

the only marginal red flag is that the author does not claim P ≠ NP in the title/ abstract but does so later in the paper. this can be taken as a sort of minor obfuscation. but it is a small stylistic crime that even great mathematicians are guilty of. (iirc) Perelman didnt directly claim to have resolved the Poincare conjecture in his earlier papers. maybe mathematicians might have some comment on this style.

have developed something like my own ratings system/ checklist. this is of course arbitrary but has some value. ofc it can lead to false positives or negatives “in theory” but in practice, is a high bar that is not often triggered, so in a sense there have been no “false negatives” so far, wrt that actually any criteria suffice (because in the sense that nobody has proven P ≠ NP yet, so any criteria that rejects all attempts is so far infallibly correct). 😛

  1. does the author have a Phd or masters?
  2. has the author done prior work in the area?
  3. what are the citations in the paper? does it cite deeper relevant theory?
  4. how responsive is the author to email/ feedback?
  5. does the author have any familiarity with natural proofs barrier, and does he have any explanation/ justification why the “proof” evades it somehow?

of course these are not foolproof measures and can be defied. but they are all easily justified. the “odds” of a non-Phd solving P vs NP are miniscule (actually/ honestly the “odds” of a Phd solving it also are miniscule, but am struggling a bit to write some non-banalities/ non-tautologies here, and whatever…). and one might think that responsivity of the author has nothing to do with correctness of the proof, but there is a concept/ tradition of a “thesis defense” in academia as a strict requirement for earning masters/ Phds for a (very good) reason.

now, is it correct? cannot say myself but can offer this blog at least. alas, the so-called “community” is so far no help in determining this—different people in the “community” may sometimes talk about the “community” but sometimes the purported “community” is nowhere to be found. papers like these require intense specialist attention to disentangle. so far there are no volunteers.

its a bit like a very long line of people all waiting for someone else to step forward so far. it takes so much work to isolate glitches in papers like these and is a mostly thankless task, and experts know the odds of correctness are so miniscule and have probably been thru it all before with the entirely predictable outcome.

yes, its strange to talk of probability of correctness on matters of logic that are either true or false, but yet its a very human response. on the other hand its disappointing that its gone ~¼ of a year with virtually no openly offered expert attention/ feedback so far. but not surprising. and in this case it shows that the Deolalikar attack was something of a singular anomaly wrt cyberspace; ie a proof attempt that went somewhat viral and quickly triggered relatively massive online peer review.

yes, there is a concept of “peer review” but that has different meanings. there is the simple meaning of the words, and there is the specialist scientific connotation, and these are often conflated because they have far different properties. the “community” can “peer review” the paper right now outside of a journal peer review in cyber-realms such as blogs, chat, social media, etc, and highly encourage that myself, but so far there are nearly/ essentially no takers/ volunteers among the experts; on the other hand at least amateur cyberspace aficionados have “discovered” and poked at it and are not completely quiet/ silent on it either.

also as noted here previously, there are a few P vs NP papers on arxiv by Phds other than Hauptmann, and the community has virtually nothing to say about them. what does this say about the academic/ Phd system anyway?

there is a sort of “omerta” aka “code of silence” in these areas within the “community.” its a sort of “elephant in the room” that there are some “offbeat” Phds who have masters/ Phd degrees even from top universities. all kinds of things/ scenarios/ juxtapositions are possible in this variegated world we live in, such as a brilliant ex-academic Phd in number theory working at Subway, occasionally making sandwiches.

and this is where the rubber meets the road and there is a disconnect and small )( unspeakable hypocrisy where all the supposedly highminded principles of scientific progress do not really carry out in the real world and get thrown out the window, and theres something of a small )( or maybe slightly bigger embarrassment or even shame in all that, a kind of shame “on the other side” that is not exactly related to incorrect proofs 😦

(that reminds me a bit of stories where famous manuscripts got submitted dozens of times to different publishers and still rejected. one such manuscript was zen and the art of motorcycle maintenance by pirsig, and it would be fun to make a longer list.)

 

a. hauptmann

5 thoughts on “Hauptmann P≠NP attack via polynomial hierarchy noncollapse”

  3. Pingback: norbert blum P vs NP attack goes CYBER-SCIENCE-VIRAL! | Turing Machine

Leave a comment