Hacker Newsnew | comments | show | ask | jobs | submit login

You must read it in context.

What it says is that if P == NP then the implications are profound for applications such as cryptography and on the general question of whether human creativity can be automated.

You can see why P == NP would have profound implications for crypto: many of our widely used techniques would turn out to, um, be easy to crack.

I believe the intent regarding human creativity is that humans often end up with a practical need to deal with some real-world instance of a size-able NP-complete problem. We don't know any way to efficiently find the optimal solution so we creatively deal with what we can figure out (the traveling salesman's optimization problem, placed into the real world, might count). Are our creative guessworks and heuristic discoveries essential? Or can automation based on P == NP eliminate the need for them - and do better than we do on these problems.




Lets assume that P==NP, why assume that we would be able to find algorithms to easily crack crypto?

Let me put it another way, lets say that we finally discover that it is possible to time travel to the past. However, the energy needed to travel back int time is the equivalent of a million Suns because that is the amount of energy needed to warp space enough so that time will reverse itself. And we found proof of this when we observed the black holes of two galaxies colliding. So, even if it were possible it would still not matter. Practically speaking, it would still not be possible to travel back in time.

My gut feeling is that if it were to turn out that P==NP that would not necessarily mean that all of a sudden we would be able to find the exact algorithms that make it easy to crack cryptography algorithms easily.

-----


We would know from the proof that such algorithms would exist, and possibly get a method from the proof as to how formulate them.

Also, gut feeling doesn't work in math. I mean, not at all.

-----


NPC algorithms are roughly equivalent, so a P solution to one is a P solution to all. So, assuming the proof would be somewhat constructive, that would give you a P solution.

But, RSA (and probably other) cryptosystems aren't even thought to be NPC to solve... so they're probably unaffected. So, I guess it depends on the implementation details of the cryptosystem. Probably it wouldn't render them wide open, but it might make previously good keys far weaker, and mean that much longer must be spent on encryption for it to be safe (rather than now where a safe key can be decoded almost instantly on an embedded platform).

-----


Polynomial doesn't mean "easy".

O(n^10000) is polynomial but really not easy.

-----




Guidelines | FAQ | Support | API | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact

Search: