4 ms·
Interesting that this is the second P!=NP proof from a University of Bonn researcher. Other one, by Mathias Hauptmann, is here: https://arxiv.org/abs/1602.0478
by ethan_g 9y ago
Interesting that this is the second P!=NP proof from a University of Bonn researcher. Other one, by Mathias Hauptmann, is here: https://arxiv.org/abs/1602.04781 https://arxiv.org/abs/1602.04781
I never did hear the status of Hauptmann's proof (I'm not connected to academia so only know what I've read on the internet), but given it's been over a year without word, presumably there's something flawed.
I might not get too excited over this proof, either, until another member of the TCS community can vouch for it. There have been many serious-looking attempts at PvNP that turn out to have fundamental flaws.
- alderz 9y agoHow does the paper of Hauptmann prove P != NP? Sigma_2^p != NP as far as I know and after a brief skimming the paper does not mention P != NP. Edit: the paper does indeed mention P != NP in the form of P != Sigma_2^p => P != Sigma_1^p = NP. Please disregard my comment.
- modalduality 9y agoP = NP implies the polynomial hierarchy collapses, thus P = Sigma2, so by contradiction P != NP.
- ndl 9y agoAlso interesting: if you look at the acknowledgements of Hauptmann's paper (at the end, just before references), he says, "I would like to thank Norbert Blum for carefully reading preliminary versions of the paper, for helpful remarks and discussions, for his guidance and patience and for being my mentor." This means Blum knew about this past attempt and presumably thought it correct enough to put on arXiv. I assume from the current paper that he has changed his mind since then.