Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: If P = NP, what does it mean?

news.ycombinator.com

Post reply on HN
Print view View original

21–30 of 37 posts

Re: Ask HN: If P = NP, what does it mean?

#21

Post by jacobolus »

Fargren wrote: post #11
klodolph wrote: post #7

Earlier quoted context omitted.

This is incorrect. You would need to find a polynomial algorithm for at least one "NP-hard" problem, not any problem in NP. And a polynomial, exact algorithm would not necessarily be superior to heuristics for relevant real-world NP problems such as 3SAT... what if the polynomial were O(N^1000)?

You are right, I confused NP with NP-hard. However, I think it's safe to assume that if a polynomial solution exists for a NP-hard problem, the complexity wouldn't be so incredibly high than it's better to use heuristics.

> I think it's safe to assume that if a polynomial solution exists for a NP-hard problem, the complexity wouldn't be so incredibly high than it's better to use heuristics.

How is this possibly safe to assume? The “heuristic” methods aim for a “good enough” solution rather than “the best solution”. Whyever would a polynomial time algorithm for exactly solving an NP-hard problem be faster than polynomial time “heuristic” algorithms (which depending on the acceptable solution quality can be relatively computationally simple)?

Re: Ask HN: If P = NP, what does it mean?

#22

Post by [deleted] »

kenjackson wrote: post #6

I think what will be really fascinating is that if statistical mechanics does end up being the mechanism that finishes the puzzle I do think that CS will have to take a much harder look at making physics a more core part of the curriculum. This would mean that the two largest results in CS in the past 20 years have both come from working with feet both in CS and physics (Shor's work on factorization with quantum comp…

[deleted]

Re: Ask HN: If P = NP, what does it mean?

#23

Post by Dn_Ab »

P = NP would touch almost every field known to man: maths (e.g. it would only be matter of search to take down the remaining Clay Problems), philosophy, engineering, biology, physics.

The tie to physics is particularly interesting: for example if Quantum mechanics was a nonlinear theory then we could physically solve NP complete problems [1]. Note the implication, this is not to say p = np => QM nonlinear. The utopian consequences of p = np are discussed very engagingly by Scott Aaronson here [2].

I suggest you also check out his blog as well - his writing style is clear and fun. Plus there was a recent discussion there that linked complexity theory to foundational physics.

[1] http://arxiv.org/abs/quant-ph/9801041

[2] http://www.scottaaronson.com/papers/npcomplete.pdf

Re: Ask HN: If P = NP, what does it mean?

#25

Post by baddox »

brown9-2 wrote: post #4

It could mean that certain problems which are known to be "difficult" (cryptography, factoring multiples of primes, traveling salesman, bin-packing, etc.) may not be inherently "difficult" and may have solutions (yet to be found) which can solve the problem in polynomial time. There are many things built on top of the fact that certain types of problems are not easily solvable - cryptography being the most obvious -…

I don't think this is necessarily true. The gap between tractable and intractable is a human convention (albeit a reasonable one). It's quite possible that polynomial-time algorithms exist that technically defeat cryptography, but they can still be practically intractable if their constant factors are astronomical.

Of course, that's still a blow to cryptography, since polynomial increases in computing power will make cryptography-breaking algorithms run meaningfully faster. Still, I don't think it would immediately devastate cryptography.

Re: Ask HN: If P = NP, what does it mean?

#26

Post by baddox »

derefr wrote: post #16
brown9-2 wrote: post #4

It could mean that certain problems which are known to be "difficult" (cryptography, factoring multiples of primes, traveling salesman, bin-packing, etc.) may not be inherently "difficult" and may have solutions (yet to be found) which can solve the problem in polynomial time. There are many things built on top of the fact that certain types of problems are not easily solvable - cryptography being the most obvious -…

Then, on a tangential note: are there classes of problems harder than NP, that we could switch to for cryptography et al. if it turned out that P = NP?

A problem harder than NP would not even be verifiable in polynomial time, which I believe would limit their practicality.

Re: Ask HN: If P = NP, what does it mean?

#27

Post by derefr »

baddox wrote: post #26
derefr wrote: post #16

Earlier quoted context omitted.

Then, on a tangential note: are there classes of problems harder than NP, that we could switch to for cryptography et al. if it turned out that P = NP?

A problem harder than NP would not even be verifiable in polynomial time, which I believe would limit their practicality.

If it was verifiable in NP time, and P = NP, then wouldn't it also be verifiable in polynomial time?

Re: Ask HN: If P = NP, what does it mean?

#28

Post by baddox »

derefr wrote: post #27
baddox wrote: post #26

Earlier quoted context omitted.

A problem harder than NP would not even be verifiable in polynomial time, which I believe would limit their practicality.

If it was verifiable in NP time, and P = NP, then wouldn't it also be verifiable in polynomial time?

Is that correct? I'm not sure. NP problems are verifiable in deterministic polynomial time. That includes the hardest of NP problems (NP-complete problems, e.g. travelling salesman and graph coloring). Are there problems that are "harder" than that? I never learned about anything outside NP—I know there are other complexity classes out there (like probabilistic classes), but I don't know how they compare to NP. My guess is that anything outside NP is essentially a non-deterministic problem altogether, meaning the "answer" isn't formally a simple "yes" or "no."

Re: Ask HN: If P = NP, what does it mean?

#30

Post by nochiel »

Before posting this question, shouldn't the author have at least done some cursory research? A quick google query, a visit to wikipedia or even to the Clay Math Institute would have led to a swift answer.

I can only conclude that the author knew this and posted the question simply to generate karma.

Such behaviour is reprehensible and should be strongly discouraged on HN.

Post reply on HN