Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Solution of the P versus NP Problem?

arxiv.org

Post reply on HN
Print view View original

191–200 of 303 posts

Re: A Solution of the P versus NP Problem?

#191

Post by ethan_g »

btilly wrote: post #137
ajarmst wrote: post #29

This is definitely one of those "I'm going to wait for the peer review" claims, but it is pretty exciting. Pros: The author is not a dilettante, and is actively researching in the area ( http://theory.cs.uni-bonn.de/blum/Forschung/forsch.var ) Cons: It's not my area, but I was expecting something a little more novel for a solution to P?NP. This almost seems too simple (it might almost fit in a margin...). Could be pr…

The paper looks like it is 38 pages and builds on other work. That doesn't seem too simple to me.

I tend to agree with GP that this is suspiciously simple. I've only skimmed it, but the novel part of the proof appears to only be Thm 5-6 which is less than 10 pages, and it's not especially dense writing. So this would be a relatively simple proof. Moreover, the technique used appears to be rather incremental over known techniques, so it's surprising it would be strong enough to prove PvNP which is so far away from the frontier of known techniques.

Re: A Solution of the P versus NP Problem?

#192

Post by DSrcl »

yters wrote: post #174

If p != np, then comp sci will lose much of its appeal. There is an underlying hope behind the field that p = np, otherwise most problems of interest are intractable, and programmers are no longer masters of the universe. This is probably why there is not a proof yet, since the truth is undesirable.

  This is probably why there is not a proof yet, since the truth is undesirable.
You are presenting an explanation to a false observation.

Re: A Solution of the P versus NP Problem?

#193

Post by westoncb »

hnaccy wrote: post #175
westoncb wrote: post #111

Earlier quoted context omitted.

Unlikely considering the author of the paper. I'm basing that on other comments on the thread which this section seems to be missing, e.g.: > ...this guy is an established senior researcher at the University of Bonn

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.

Re: A Solution of the P versus NP Problem?

#194

Post by nabla9 »

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.

Re: A Solution of the P versus NP Problem?

#195

Post by johnhenry »

bmh_ca wrote: post #11
NikolaeVarius wrote: post #5

Earlier quoted context omitted.

>> This implies P not equal NP.

> This implies P not equal NP I did some graduate level research on P =? NP, specifically in the SAT space " rel="nofollow">https://en.wikipedia.org/wiki/Satisfiability> . In particular, I helped design MARMOSET (Marmoset Automated Reasoner Mostly Only Solves Easy Theorems), a competitive SAT problem solver. " rel="nofollow">http://www.cs.unb.ca/research-groups/argroup/marmoset/> . (It's a cool name... I didn't come…

I'd challenge you on that second one. There's literally a million dollar prize for out this one. Lots of people are interested. https://en.wikipedia.org/wiki/Millennium_Prize_Problems#P_ve...

Re: A Solution of the P versus NP Problem?

#196

Post by kevinnk »

nieve wrote: post #116
WhitneyLand wrote: post #72

Earlier quoted context omitted.

It shouldn't be career ending unless there's been malfeasance or some kind of sloppy work. The people who go down hard usually have some crime beyond audacity. It could easily cause some painful embarrassment, but hopefully that would pass with time. Maybe embarrassment similar to that faced by researchers who's results suggested FTL communication, but it turned out to be a bad fiber-optic cable. I didn't follow up b…

I wouldn't be surprised if they gained a bit of respect. If I recall correctly they did everything right - they had an apparently impossible result, they spent a lot of time trying to disprove it, and when they announced they made it clear that they doubted the result. Hiding it because they were sure it was false, but couldn't disprove would have been poor science. It had to be pretty scary to make that announcement…

Actually, there was a bunch of blow back and the main researchers behind the result stepped down.

https://www.newscientist.com/article/dn21656-leaders-of-cont...

Re: A Solution of the P versus NP Problem?

#197

Post by jacquesm »

jl6 wrote: post #101
lisper wrote: post #52

Earlier quoted context omitted.

FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

This lines up perfectly with most software bugs. Hard to find, but once you have them easy to prove they are the cause of the problem. The difference is that in software bugs are usually fairly easy to fix, a math proof with a bug in it might not be fixable at all.

Re: A Solution of the P versus NP Problem?

#198

Post by mihaild »

kevinwang wrote: post #179
Gehinnn wrote: post #163

Earlier quoted context omitted.

Actually, we already know an algorithm that solves an NP complete problem in polynomial time iff P = NP. We can just enumerate all programs and ask them to generate witnesses. As we can decide whether a witness is valid and there is a program that always outputs a valid witness if P=NP, we can find that program within finite steps and the algorithm is correct.

Correct me if I'm wrong, but enumerating all programs doesn't seem polytime

Formally, we run all possible programs in parallel: the 1st program runs for 1 step; the 1st and 2nd programs run for 1 additional step; programs 1-3 run for 1 additional step; ... After program stops, we check if its output is our witness. If there is program number K running in time f(n), then our program runs in time O(K * f^2(n) * [simulation time] * [check time]), which is polynomial if f is polynomial.

Re: A Solution of the P versus NP Problem?

#199

Post by evincarofautumn »

soberhoff wrote: post #177
Filligree wrote: post #148

Earlier quoted context omitted.

I don't think it would be possible to make finding it as easy as verifying it, but how can we prove that?

Finding flaws in proofs is as easy as verifying them. After all, finding a flaw amounts to just checking a proof. Finding a proof is the truly hard challenge.

Checking a proof isn’t necessarily easy, of course, in the sense of both human hardness—such as requiring a lot of background, using dense notation, or being very long—and computational hardness, such as using a logic whose decision procedure takes exponential time.

Re: A Solution of the P versus NP Problem?

#200

Post by credit_guy »

cvoss wrote: post #49
teton_ferb wrote: post #33

Earlier quoted context omitted.

Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve ? (P)". Note that the reverse is obviously true : problems that are easy to solve are also easy to verify . Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the…

(You may have omitted this detail on purpose, but I think it's worth pointing out) The example of trial division as a primality test is a good illustration of an algorithm that takes a lot of work to run but whose output is easy to verify. However, the problem of primality testing is actually in P. [1] You have to use a fancier algorithm than trial division in order to get polynomial time. [1] https://en.wikipedia.or…

another detail that the GP most likely left out on purpose is that the fact that easily checking divisibility means that primality is co-NP. Primality being NP is actualy non-trivial (even before AKS). see wikipedia for more details: https://en.m.wikipedia.org/wiki/Primality_certificate
Post reply on HN