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

31–40 of 303 posts

Re: A Solution of the P versus NP Problem?

#31

Post by nerdponx »

zolthrowaway wrote: post #21
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…

Beyond crypto, problems like the traveling salesman would also be solvable in polynomial time.

Re: A Solution of the P versus NP Problem?

#32

Post by bradleyjg »

davewritescode wrote: post #20
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.

Intuitively, almost everyone assumes that P != NP but it's been incredibly difficult to prove. If P == NP were proved it would be earth shattering, because lots of difficult problems may become solvable.

Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)?

Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.

Re: A Solution of the P versus NP Problem?

#33

Post by teton_ferb »

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?

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 answer 5 and comparing it with your answer. So we can conclude "Problems that are easy to solve are easy to verify" In other words, P ⊆ NP.

_Now is the reverse true? Are problems that are easy to verify also easy to solve?_

Let me give you an example. Let us assume that the question is "Is 1053188576519689 prime?". You come back and tell me, "No it is not prime, it is divisible by 32,452,867".

1) It is easy to verify your solution. I can divide 1053188576519689 by 32,452,867 and verify that it is indeed divisible. 2) It is hard to solve the problem, I have to try out numbers from 2,3,...,sqrt(1053188576519689), which is quite painful. (Or maybe there is as yet undiscovered better algorithm). So it appears that problems that are easy to verify may not be easy to solve. Or it appears that NP ⊆ P is not true. In other words, it appears P != NP (because if P ⊆ NP and NP ⊆ P, P == NP).

NP problems have wide ranging applications in things like cryptography for example. Let us assume I have a hashing technique. It is easy to hash a document, but hard to reconstruct the document from the hash. Then this technique can be used in auctions where you do not trust the auctioneer. You publicly submit the hash of your bid before the deadline. You do not submit your bid itself, because you are afraid that the person handing out the contracts will reveal the number to his brother-in-law who will bid $1 more than you and win the contract. After the deadline is passed, you send your actual bid to the Auctioneer.

Now 1) Everyone can verify that the documents have not been altered (the hashes are posted publicly, each document can be hashed and compared with its publicly posted hash). So it is easy to verify that the documents have not been tampered with after the deadline.

2) Nobody can construct the document from the hash. So it is not easy to solve for the bid document given the hash. So everyone can post the hash publicly with confidence before the deadline.

If P != NP we can have this type of auctions. If P == NP then there is no difference between posting the hash publicly and posting the document publicly.

Re: A Solution of the P versus NP Problem?

#34

Post by jxramos »

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…

+1 like the reference to Fermat's ghost here and all those connotations in that short ponder.

Re: A Solution of the P versus NP Problem?

#35

Post by jakeogh »

bradleyjg wrote: post #32
davewritescode wrote: post #20

Earlier quoted context omitted.

Intuitively, almost everyone assumes that P != NP but it's been incredibly difficult to prove. If P == NP were proved it would be earth shattering, because lots of difficult problems may become solvable.

Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)? Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.

related to https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...

Re: A Solution of the P versus NP Problem?

#36

Post by teton_ferb »

teton_ferb wrote: post #33
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?

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…

Also wanted to say:

People have been taking a go at this for many years now. Grapevine says that several large CS departments in many countries have groups of graduate students devoted to solving sub-problems of the entire proof because it is a prestige issue. Extraordinary claims require extraordinary proof and any proof will go through multiple peer reviews.

Perelman's proof of Poincare Conjecture was studied for several months before being declared true (~3 years) and that was considered "fast". https://en.wikipedia.org/wiki/Grigori_Perelman#Perelman.27s_...

Re: A Solution of the P versus NP Problem?

#37

Post by lvh »

yifanlu wrote: post #7

Just a half minute skim shows the author claims it passes the natural proof barrier but makes no claim about it being non-relativizing or non-algebraizing.

For those following along at home: this is important because we have a proof that relativizing wouldn't work. In this context, relativizing means relative to an oracle. For example, P^A means "just like a Turing machine would regularly recognize languages except this one has a magical oracle that can recognize A in one step". A can be arbitrarily complex, including NP-complete ones like 3SAT.

This is important because the Baker-Gill-Solovay theorem already demonstrates that there exist oracles A != B relative to which P^A = NP^A, but P^B != NP^B. This shows that the problem has contradictory relativizations, and hence can't be proven that way. This matters because it's a litmus test against quack proofs.

I don't think this is a problem here; the proof doesn't appear to be doing that.

Re: A Solution of the P versus NP Problem?

#38

Post by kobeya »

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.

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

#40

Post by dhosek »

bmh_ca wrote: post #30
hnaccy wrote: post #12

Earlier quoted context omitted.

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

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.
Post reply on HN