Hacker News Reader

Comment by enriquto | Hacker News Reader

You wrote this:

> For example, breaking almost any cryptographic code can be phrased as an NP problem. So if P=NP—and if, moreover, the algorithm that proved it was “practical” (meaning, not n^1000 time or anything silly like that)—then all cryptographic codes that depend on the adversary having limited computing power would be broken.

Can you explain this reasoning more precisely? The class P contains difficult problems that require O(n^googolplex) algorithms, so are not solvable in practice. The fact that P=NP would not make these problems any easier.

View on HN

He explicitly says «not n^1000 time or anything silly like that» in the sentence you quote, n^googolplex would be way more silly

my point exactly. The class P contains this silly stuff.

He's already covered that; not sure what's left to explain: he's said that if P=NP and if we get there with a practical running time algorithm (e.g. one that solves 3SAT in O(n^4) or something, and with reasonable constants too), then such-and-such consequences. So what are you asking?

The second part of the claim seems much, much stronger than the first part, but he makes it sound like it's a minor detail. I am confused as to why.

The claim was that "all cryptographic codes that depend on the adversary having limited computing power would be broken."

Here's a (very slightly) more rigorous justification:

If P=NP, then any NP problem is in P with at most a polynomial slowdown. That is, if there's an algorithm taking T steps on a non-deterministic Turing machine, we can solve it on a deterministic Turing machine in f(T) steps, where f is a polynomial. Presumably, a "practical" algorithm would be one for which f has a low degree.

The kinds of algorithms we're concerned about in cryptography (and plenty of other fields) already have low time complexity. For example, generating or verifying an HMAC is O(n) in the length of the input. So if we had a way to solve NP problems with a low-degree polynomial slowdown, we could break HMACs in low-degree polynomial time.

It doesn't matter that there are O(n^1000) problems out there that would still be realistically unsolvable, because those problems don't have practical applications in the first place.

I believe section 1.2.1 of Scott's P ?= NP survey addresses your question:

https://www.scottaaronson.com/papers/pnp.pdf

Yup

Reply on news.ycombinator.com