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

41–50 of 303 posts

Re: A Solution of the P versus NP Problem?

#41

Post by enriquto »

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.

This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.

Re: A Solution of the P versus NP Problem?

#42

Post by adrianmonk »

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?

Some people will hold it against him because some people are too stupid to see things in context. Rather than respecting him for taking a smart risk in pursuit of an important goal, they will just remember that he was once wrong about something and in a big way.

There are people who point at others' failures to bolster their own image by comparison. And there are people with fragile egos who are eager to see others in a negative way.

It shouldn't be that way, but it sometimes is, so I wouldn't say the career risk is zero. But I'm still glad he's doing it regardless of the outcome.

Re: A Solution of the P versus NP Problem?

#43

Post by hervature »

x3n0ph3n3 wrote: post #24
hervature wrote: post #16

Earlier quoted context omitted.

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.

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?

#44

Post by Govindae »

nerdponx wrote: post #31
zolthrowaway wrote: post #21

Earlier quoted context omitted.

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.

Well... The traveling salesman decision problem, not the general case.

The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum.

What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.

Re: A Solution of the P versus NP Problem?

#45

Post by bradleyjg »

jakeogh wrote: post #35
bradleyjg wrote: post #32

Earlier quoted context omitted.

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

That was really entertaining, thanks for linking it.

I especially liked this bit:

David Johnson famously once said, For any instance {G = (V, E)} that one could fit into the known universe, one would easily prefer {|V |^{70}} to even constant time, if that constant had to be one of Robertson and Seymour’s.

I was curious so I tracked down this:

Johnson estimated that the hidden constant is “somewhat larger” than 2 ⇑ (2 ⇑ (2 ⇑ (h/2)) + 3), where 2 ⇑ t denotes an exponential tower of t 2s (2 ⇑ 0 = 1 and 2 ⇑ t = 2^2⇑(t−1)) and h is the number of vertices in H.

Re: A Solution of the P versus NP Problem?

#46

Post by OJFord »

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.

It's generally not the case though: problems that arise 'naturally', i.e have not been constructed to counter my forthcoming point, in P seem to be of low order.

If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?

Re: A Solution of the P versus NP Problem?

#47

Post by wolfgke »

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.

> Intuitively, almost everyone assumes that P != NP

Donald Knuth believes P = NP.

Source: http://www.informit.com/articles/article.aspx?p=2213858&WT.m... (question 17). Also cf. https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP

Re: A Solution of the P versus NP Problem?

#48

Post by deong »

enriquto wrote: post #41
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.

This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.

This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. An n*log(n) algorithm does a divide and conquer step for each input. Moving to the exponential world, you have the 2^n "tries all combinations" and n! "tries all orderings" type algorithms, which again, make sense both as mathematical functions as well as behaviors that constitute sensible algorithms.

What does an O(n^10,000) algorithm do? What understandable problem yields a solution that behaves that way?

Re: A Solution of the P versus NP Problem?

#49

Post by cvoss »

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…

(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.org/wiki/AKS_primality_test

Re: A Solution of the P versus NP Problem?

#50

Post by lisper »

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.

There's a third possibility: there's a flaw in the proof, but one that is hard to find, and the discovery of the flaw actually advances the field in interesting ways.

If I were a betting man that's actually where I'd put my money because the paper passes by bogometer test (but I am nowhere near qualified to assess whether it's actually correct).

Post reply on HN