News for hackers. Stuff that matters.
Re:A Solution of the P versus NP Problem? by hnaccy on Monday August 14, 2017 @01:04PM (#15010313)
>Nobody's really interested in a proof that P != NP.

I doubt that.

Re:A Solution of the P versus NP Problem? by hervature on Monday August 14, 2017 @01:31PM (#15010564)
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.
Re:A Solution of the P versus NP Problem? by hnaccy on Monday August 14, 2017 @01:47PM (#15010721)
A proof would likely involve novel techniques and open up new areas of research.
Re:A Solution of the P versus NP Problem? by dom0 on Monday August 14, 2017 @01:36PM (#15010619)
There are a bunch of major assumptions which are not rigorously proven, but generally assumed (hence assumption) to be correct, frequently backed up by a large body of heuristic evidence.

P!=NP is one of them.

Re:A Solution of the P versus NP Problem? by x3n0ph3n3 on Monday August 14, 2017 @01:45PM (#15010698)
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? by hervature on Monday August 14, 2017 @02:22PM (#15011078)
The difference is that if Riemann Zeta is incorrect, many theorems that are based on the hypothesis being correct will also be invalidated. Whereas assuming P != NP is limited to a relatively small area of complexity theory. I think a much more equivalent conjecture in complexity theory would be the unique games conjecture. Because the unique games conjecture already provides certain problems to be completely characterized (see: https://en.wikipedia.org/wiki/Unique_games_conjecture#Releva...). Thus, proving this to be true kind of closes the chapter on many problems. Whereas proving P != NP true still leaves many gaps open.
Re:A Solution of the P versus NP Problem? by kobeya on Monday August 14, 2017 @02:16PM (#15011027)
> Nobody's really interested in a proof that P != NP.

This is not the case. In my day job I need to worry about what happens if ECDSA is broken. One way that can happen is quantum computation -- but that has a relatively transparent development timeline we can plan for. The other way in which ECDSA could be broken is if P==NP and the discrete log problem can be transformed in polynomial time into another polynomial time algorithm. All of our customer funds could be stolen at that point, with liabilities in the hundreds of millions or billions of dollars.

That's lot of customer money on the line if that happened. My employer might need to pay BIG money for insurance against a P==NP break of ECDSA, or else risk going bankrupt if it happened. A proof of P!=NP would translate directly into cost savings, either in not getting that insurance or in drastically reducing premiums for it.

Re:A Solution of the P versus NP Problem? by fpoling on Monday August 14, 2017 @03:38PM (#15012042)
Knowing P?NP does not imply much in practice unless the answer precisely bounds complexity. N^(N*1e-100) is exponential yet very practical while N^1e100 is polynomial yet is useless in this Universe.
Re:A Solution of the P versus NP Problem? by kobeya on Monday August 14, 2017 @06:04PM (#15013435)
Knowing P!=NP is immensely practical however.
Re:A Solution of the P versus NP Problem? by bmh_ca on Monday August 14, 2017 @01:59PM (#15010866)
> I doubt that.

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

Re:A Solution of the P versus NP Problem? by gregfjohnson on Monday August 14, 2017 @03:02PM (#15011567)
Your clarification makes sense - a PhD advisor with a bit of NSF or other grant money would likely only fund a grad student to work on a problem that has a reasonable likelihood of generating some concrete, positive, and publishable results. This typically means an incremental result on a problem of interest to the research community.

That having been said, an accepted proof that P != NP would result in a Turing award and an additional $1M for solving one of the seven Millenium Prizes. This has been an open problem for decades, and it is a problem of enormous importance and visibility.

Re:A Solution of the P versus NP Problem? by dhosek on Monday August 14, 2017 @02:17PM (#15011037)
Although that might be based on the perceived likelihood of success. After all, pre-Wiles, I doubt there was much chance of a grad student getting funding to prove Fermat. Nor is a grad student likely to get funded to prove the Riemann Hypothesis.
Re:A Solution of the P versus NP Problem? by Blaisorblade0 on Wednesday August 16, 2017 @09:32PM (#15032970)
Because (I'd guess, as a PhD student in another CS field) any advisor worth its salt would advise a grad student to work on something else first, get tenure, and then maybe approach this problem. Until yesterday, most researchers agreed that the problem was unapproachable. Nowadays being a researcher is a job that requires steady progress, so you must focus on approachable problems. For P vs NP there are tons of results on classes of techniques that _cannot_ work—you'd have to learn those first to make a serious attempt.