Hacker News Reader

Comment by brown9-2 | Hacker News Reader

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 - so if it could be proved that algorithms that make these problems easily-solvable could exist, it would shatter the line of thinking about these types of problems.

The way I like to think about NP is: are there certain types of problems which we, as smart as we might be, cannot easily solve, not because we aren't smart enough but because of the nature of the problem itself?

(I have no formal education in this area so this is just my layman's attempt at an answer)

View on HN

> The way I like to think about NP is: are there certain types of problems which we, as smart as we might be, cannot easily solve, not because we aren't smart enough but because of the nature of the problem itself?

That's not entirely accurate. There are many problems that are untractable (i.e. can't solve them because of the nature of the problem) but have nothing to do with P=NP. Consider the halting problem, for instance.

There are many problems that are untractable (i.e. can't solve them because of the nature of the problem) but have nothing to do with P=NP

Can you elaborate some more on this? I'd like to learn more about this area. Are you referring to problems for which no polynomial time solution exists, and there is also no polynomial time method for verifying a solution?

I was merely responding to your sentence:

If you read it one way, it sounds as if P=NP would allow us to solve every formal problem. It doesn't. One very interesting example:

The concept of Kolmogorov Complexity. I'm not a CS theorist, so I can only give my layman interpretation, but if I understand it well it goes like this: given a particular string of bits, the Kolmogorov Complexity relates to the shortest possible program that can describe this string. In effect, that means: the ultimate compression. Well, the whole theory of KC says that you can't find this shortest possible program for every string. Not because it takes too much time to check very possible combination (P=?=NP) but because of the nature of the problem.

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.

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

but wouldn't it be just plain NP then

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.

Thanks for the explanation. I'd glanced at the article; didn't immediately 'get' it and didn't feel I had time to read further.

Reply on news.ycombinator.com