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

11–20 of 37 posts

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

#11

Post by Fargren »

klodolph wrote: post #7
Fargren wrote: post #5

Earlier quoted context omitted.

If P were to be equal to NP and we found a polynomial algorhythm to just one NP problem, then through polynomial conversion, we should be able to solve all, or at least most, NP problems in polynomial time. This would be very superior to heuristics even for the most naive of implementations for most relevant NP problems.

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.

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

#15

Post by stralep »

StavrosK wrote: post #10
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)?

NP-complete, actually. NP-hard problems don't have NP-complete equivalents.

NP-Complete are NP-Hard, inside NP.

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

#16

Post by derefr »

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?

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

#18

Post by meastham »

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?

There are classes of problems harder than NP. However, the problem of cracking any useful encryption algorithm is always going to be in NP. If it weren't, then decrypting a message would not be possible in polynomial time.

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

#19

Post by StavrosK »

stralep wrote: post #15
StavrosK wrote: post #10

Earlier quoted context omitted.

NP-complete, actually. NP-hard problems don't have NP-complete equivalents.

NP-Complete are NP-Hard, inside NP.

Some NP-hard problems are NP-complete, but not all. I guess I should have said strictly NP-hard, thanks.
Post reply on HN