Page 1 of 1

No Longer a potential proof of P != NP

Posted: Tue Aug 15, 2017 7:16 pm UTC
by Sizik
Abstract wrote:Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev's function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.


https://arxiv.org/abs/1708.03486

Re: Potential proof of P != NP

Posted: Wed Aug 16, 2017 10:32 am UTC
by Tub
Proofs about this are very common, Odds are that this one is just as flawed as the others.

There's already a discussion over at reddit. I don't see anyone pointing out the fatal flaw (yet), but the proof doesn't pass the basic smell tests that you'd expect a valid proof to pass.

Re: Potential proof of P != NP

Posted: Thu Aug 17, 2017 9:03 pm UTC
by quantropy
Some years ago I went to this talk, where the idea was that an NMR spectrometer could implement a NAND gate, and so was in a sense a universal computer. The NMR machine was connected to a computer but we were supposed to believe that the computer, which was full of logic gates, wasn't doing any of the work. I had my doubts, and I think it highly likely that the computer was acting as a NOT gate.

My point is that it is all to easy to forget how powerful NOT is. Now there is a proof which says that a proof based on monotone boolean networks (which I understand to mean networks without NOT), can be twerked a bit to apply to networks which include NOT.

I find that highly unlikely.

Re: No Longer a potential proof of P != NP

Posted: Fri Sep 01, 2017 1:54 am UTC
by Sizik
They've updated with the following comment
The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage