## No Longer a potential proof of P != NP

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Sizik
Posts: 1255
Joined: Wed Aug 27, 2008 3:48 am UTC

### No Longer a potential proof of P != NP

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
Last edited by Sizik on Fri Sep 01, 2017 1:53 am UTC, edited 1 time in total.
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

### Re: Potential proof of P != NP

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.

quantropy
Posts: 194
Joined: Tue Apr 01, 2008 6:55 pm UTC
Contact:

### Re: Potential proof of P != NP

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.

Sizik
Posts: 1255
Joined: Wed Aug 27, 2008 3:48 am UTC

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

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
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.