Hacker News Reader

Comment by NikolaeVarius | Hacker News Reader

>> 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 <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. <http://www.cs.unb.ca/research-groups/argroup/marmoset/> . (It's a cool name... I didn't come up with it :))

The conclusion I drew was:

1. P != NP because you can convert in polynomial time every SAT problem down to Horn clauses, which are P to solve, plus non-Horn clauses that cannot be converted i.e. have intractable intrinsic NP complexity whose reduction to the polynomial space requires "clairvoyance" of the quantum computation variety.

2. Nobody's really interested in a proof that P != NP.

That said, I only spent a couple years at it, and my memory may be faulty and I might change my mind if I revisited the issue. Part of me has always felt that the Horn clause reduction is a first step to isolating problems for a next step, but again — it's been a long time.

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

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.

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.

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.

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

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.

Knowing P!=NP is immensely practical however.

> I doubt that.

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

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.

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.

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.

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

> In particular, I helped design MARMOSET (Marmoset Automated Reasoner Mostly Only Solves Easy Theorems), a competitive SAT problem solver. [...]

Now that is some good SAT solver name - keeping user's expectations low, I guess? Nice choice! ;)

Reply on news.ycombinator.com