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

User avatar
Sizik
Posts: 1159
Joined: Wed Aug 27, 2008 3:48 am UTC

No Longer a potential proof of P != NP

Postby Sizik » Tue Aug 15, 2017 7:16 pm UTC

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.
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: 323
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Potential proof of P != NP

Postby Tub » Wed Aug 16, 2017 10:32 am UTC

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: 191
Joined: Tue Apr 01, 2008 6:55 pm UTC
Contact:

Re: Potential proof of P != NP

Postby quantropy » Thu Aug 17, 2017 9:03 pm UTC

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.

User avatar
Sizik
Posts: 1159
Joined: Wed Aug 27, 2008 3:48 am UTC

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

Postby Sizik » Fri Sep 01, 2017 1:54 am UTC

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
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.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 4 guests