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

21–30 of 303 posts

Re: A Solution of the P versus NP Problem?

#21

Post by zolthrowaway »

choxi wrote: post #14

What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security.

We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.

Re: A Solution of the P versus NP Problem?

#22

Post by openloop »

ianai wrote: post #10
js8 wrote: post #3

Earlier quoted context omitted.

> A career-ending disaster Why? Why should posting a stab at a complicated problem should be considered career-killing?

Seriously, best way to ensure people stop trying is to persecute attempts.

What he said.

Re: A Solution of the P versus NP Problem?

#23

Post by Analemma_ »

RSchaeffer wrote: post #6

Can someone ELI5 what this problem is, how likely the proof is to hold up to scrutiny, and whether P != NP follows?

Scott Aaronson has done some really good write-ups about P-NP, including what it means and what avenues of proof are possible. I'd start here: http://www.scottaaronson.com/papers/pnp.pdf. It probably doesn't count as "ELI5", but it's something.

Re: A Solution of the P versus NP Problem?

#24

Post by x3n0ph3n3 »

hervature wrote: post #16
hnaccy wrote: post #12

Earlier quoted context omitted.

>Nobody's really interested in a proof that P != NP. I doubt that.

I believe what they are saying is that the entire field just assumes P != NP and so if the proof came to be P != NP, then most people would just have their inklings confirmed and that's about it. It wouldn't really cause a shift in research in any of the CS departments. However, if P = NP, you can bet on a renewed interest in finding polynomial time algorithms.

That's like saying no one is interested in a solution to the Riemann Zeta Hypothesis. It's thought to be true, and mathematics have been derived from its assumed truth, but there is still major interest in proving it to be true.

Re: A Solution of the P versus NP Problem?

#25

Post by hnaccy »

hervature wrote: post #16
hnaccy wrote: post #12

Earlier quoted context omitted.

>Nobody's really interested in a proof that P != NP. I doubt that.

I believe what they are saying is that the entire field just assumes P != NP and so if the proof came to be P != NP, then most people would just have their inklings confirmed and that's about it. It wouldn't really cause a shift in research in any of the CS departments. However, if P = NP, you can bet on a renewed interest in finding polynomial time algorithms.

A proof would likely involve novel techniques and open up new areas of research.

Re: A Solution of the P versus NP Problem?

#26

Post by shurcooL »

js8 wrote: post #3
jjgreen wrote: post #2

I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.

> A career-ending disaster Why? Why should posting a stab at a complicated problem should be considered career-killing?

I think he means if the stab is not serious but a troll. Of course, if it's a genuine and serious attempt, I don't think it should be frowned upon at all.

Re: A Solution of the P versus NP Problem?

#27

Post by [deleted] »

hervature wrote: post #16
hnaccy wrote: post #12

Earlier quoted context omitted.

>Nobody's really interested in a proof that P != NP. I doubt that.

I believe what they are saying is that the entire field just assumes P != NP and so if the proof came to be P != NP, then most people would just have their inklings confirmed and that's about it. It wouldn't really cause a shift in research in any of the CS departments. However, if P = NP, you can bet on a renewed interest in finding polynomial time algorithms.

[deleted]

Re: A Solution of the P versus NP Problem?

#29

Post by ajarmst »

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 pro or con: Single author. It's becoming rare for important new work to not have multiple authors, especially from professional academics. However, Andrew Wiles...

Re: A Solution of the P versus NP Problem?

#30

Post by bmh_ca »

hnaccy wrote: post #12
bmh_ca wrote: post #11

Earlier quoted context omitted.

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

>Nobody's really interested in a proof that P != NP. I doubt that.

> I doubt that.

Let me clarify: Nobody appeared to be interested in funding a graduate student to prove P != NP.

Post reply on HN