A Solution of the P versus NP Problem?

Post by sean2 » Tue, Aug 15, 2017, 1:43 AM UTC

nabla9 wrote: post #194

If established researcher in the field makes a breakthrough of this magnitude I would expect rumors to start to circulating first. Showing the draft to few colleagues to see if they can spot mistakes before 'shaking the world' is probably a good idea.

  If his proof is correct, he gets unending fame, millions in prize money.

  If his proof is laughably flawed, he'll promptly be forgotten as one of the 100s who have been wrong before him.

  If his proof is correct, he may end up sharing credit, maybe they'll even publish his work quietly under their own name while he's still waiting for feedback. Maybe that is what we are reading now.

  If his proof is laughably flawed, then they'll give him his feedback and only his peers, instead of the whole internet will laugh at him for a day, before it's all forgotten.

Post by slaymaker1907 » Tue, Aug 15, 2017, 2:04 AM UTC

dom0 wrote: post #144

contradictioned wrote: post #120

Earlier quoted context omitted.

I want to add another important aspect, the aspect of NP completeness. There is a bunch of problems considered "NP complete" and they are all related such that it is easy to translate one problem into another (easy as in "quickly"). This means, first: If P == NP, then all of these problems become easy, and second: if P == NP and we find an algorithm that solves only one of the NP complete problems quickly, then this…

NP completeness kinda works around the uncertainty of PxNP (with x ∈ {⊆, ⊊}), because it defines some sort of "weak subset" of NP comprised of "pretty sure these problems are not in P[, because no one yet thought of a polynomial reduction to a problem in P]". The last part in brackets is the catch here; if we could show that it is not possible, then P!=NP would immediately follow, and NP completeness would become a l…

Post by KGIII » Tue, Aug 15, 2017, 2:12 AM UTC

westoncb wrote: post #193

hnaccy wrote: post #175

Earlier quoted context omitted.

Even experienced people can make "silly" mistakes. https://arxiv.org/abs/1612.04208v1

They can —but that doesn't mean we should assume it's a silly mistake (as opposed to a deep one) without more information than that he's an accomplished researcher.

Post by PrunJuice » Tue, Aug 15, 2017, 2:17 AM UTC

Halved wrote: post #182

liberte82 wrote: post #155

Earlier quoted context omitted.

Someone should research and write a paper about it.

But then how will we know that paper is correct?

Post by dbaupp » Tue, Aug 15, 2017, 2:27 AM UTC

sova wrote: post #189

mbrubeck wrote: post #166

Earlier quoted context omitted.

A simple but wrong proof of "P = NP" is easier to write in some ways, since you "just" need to provide a single algorithm for one NP-hard problem, and show that it runs in polynomial time. It looks like many or most of the proof attempts in that list take this form. A plausible proof of "P != NP" won't be quite as simple to express, since it needs to prove that all such algorithms do not run in polynomial time.

Well yes! Two things: You have a successful algorithm that runs in P time that solves an NP Hard problem and 2) you can map other NP Hard problems to your problem. Without the second factor, it is only a demonstration of a "range" in the computational realm in question, where p = np or whatever the declaration. Being able to show that your pizza slice is actually an ocean of pizza, and also show that any other shape…