Hacker News Reader

Comment by aruss | Hacker News Reader

It's a decent introduction to P vs. NP but gets a few things wrong: factoring is technically an NP problem, but it's not (known to be) NP-complete, and packet routing is a pathfinding problem rather than a TSP, which is distinctly in P.

Also it should probably address the silly arguments that pop up that there's no bounds on the exponent for the runtime of an algorithm (O(n^100) is still in P), but this doesn't and hasn't happened in practice. And the implications for security would be huge because we would have to redefine what we mean by provable security, and then have to make some other arbitrary distinction. Is n^100 secure, but n^99 not? How does parallelization affect runtime? Things become a lot messier. So for now P vs NP is an extremely useful distinction and I have yet to see a convincing argument that it's not.

View on HN

"there's no bounds on the exponent for the runtime of an algorithm (O(n^100) is still in P), but this doesn't and hasn't happened in practice."

That n^100 doesn't happen in practice might very well be selection bias. Perhaps humans are really bad at finding solutions that genuinely require polynomial work greater than O(n^4) [see note 1]. In fact, if P=NP, that would explain why we haven't thus-far found the polynomial time algorithms for any NP-complete problems.

"we would have to redefine what we mean by provable security, and then have to make some other arbitrary distinction. Is n^100 secure, but n^99 not?"

That doesn't seem materially different than having to pick key lengths. There is some amount of work you expect to be beyond what your opponents could theoretically muster. Pad a bit for safety.

"So for now P vs NP is an extremely useful distinction and I have yet to see a convincing argument that it's not."

We're using NP as a proxy for "provably different lower bound on checking versus finding". It's not a bad proxy, but having an actual proof of lower bound should be even better whether or not it is exponential, provided there's a sufficient gap to make realistic key sizes useful.

[1] Edited to add: As pointed out to me below, there are plenty of examples of O(n^k) with arbitrarily high k. This certainly undermines my speculation about human capabilities. At the same time, it means it does happen in practice.

There are plenty of algorithms with n^k where k>4, just not useful ones.

Off the top of my head, checkout work by Eric D. Demaine. His work is on problems that seem very real, and solutions (algorithms) definitely show very lovely interaction of several different areas of research, problem solving skills at its finest.

http://cstheory.stackexchange.com/questions/6660/polynomial-...

Thanks! That weakens my speculation about human capabilities, though the fact that it deserves calling out as "problem solving skills at its finest" seems to leave me some wiggle room ;)

To be honest, I'm not sure how to quantify the relative populations of higher-exponent and lower-exponent found algorithms, and if there is a skew some of that might well be due to the decreased attention to the space of higher exponent algorithms due to lower expected usefulness...

In cryptography, the goal is not to find problems that require O(n^k) steps to solve, but to find trapdoor one-way function families (the basis of public key cryptography) where the easy direction is O(n) and the hard direction (without the private key) is O(n^k) for arbitrarily high k.

This would be easier to prove than O(exp(n)) and may even be quantum-computer resistant but I'm not sure if there are such cryptosystems, and if there are, they're not in common use since traditional models assume a polynomially strong adversary (as assumption we may want to relax).

Right, relaxing the "it must grow faster than polynomial" might free up some new methods that we've foregone. But it's also the case that existing methods might still work fine - breaking them wouldn't be Omega(exp(n)), but may still have a high enough lower-bound for realistic values.

Of course, if we discover that P=NP, getting at those lower bounds would be a priority...

> I have yet to see a convincing argument that it's not

http://www.informit.com/articles/article.aspx?p=2213858

Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in nM elementary steps. ... My main point, however, is that I don't believe that the equality P = N P will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M. ... The moral is that people should distinguish between known (or knowable) polynomial-time algorithms and arbitrary polynomial-time algorithms. People might never be able to implement a polynomial-time-worst-case algorithm for satisfiability, even though P happens to equal N P.

On the other hand, there's Scott Aaronson's "The Scientific Case for P≠NP"[1]:

"So, OK, why should you believe P≠NP? Here’s why:

"Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false."

[1] http://www.scottaaronson.com/blog/?p=1720

I think they're agreeing on the major substantive issue, that we won't reach a world where "composing a symphony is just as easy as enjoying it" -- Aaronson, because P != NP, and Knuth, because the proof of P=NP will not provide a polynomial-time algorithm for NP-complete problems.

This symphony thing comes up again and again but it seems pretty silly to me. Enjoying and composing a symphony requires understanding what makes a piece of music sound good to humans, undoubtedly a nontrivial problem, but is it really hard to imagine that once that got formalized one can use this information to search the space of all possible pieces of music for beautiful symphonies in a not terrible inefficient way? I don't think so.

That's not too surprising. Most NP-hard problems are pretty tractable in practice.

But is that a convincing argument? His argument seems to be that he can come up with a integer M that is so unimaginably large that we can surely solve any n bit problem in NP space in n^M steps. Knuth himself prefaces his argument by saying that it is naive!

His main point, which is more about the practical effects of P=NP is much more convincing, and actually very common I believe.

The argument is not only unconvincing, it is incorrect. The time hierarchy theorem implies the existence of problems of difficulty n^M for arbitrary M, and all those problems are clearly in NP.

The time hierarchy theorem does not state that there are NP-complete problems that cannot be solved in polynomial time. If it stated that and was well-accepted, then there would be no P ?= NP mystery.

Correct, but I didn't claim what you are refuting. I just said that there is no upper bound to "how polynomiallly hard" a problem can get, i.e. Knuths intuition is wrong.

Look at the quote. Knuth is explicitly only talking about NP problems.

> Is n^100 secure, but n^99 not?

Is 128 bits secure, but 127 not?

At some point you have to arbitrarily pick a threat model. Pick a budget, a number of decades of Moore's law, and how big of an extra buffer you want. Then pray there are no gaping algorithmic flaws.

This is the same whether you're looking at O(n^7) or O(2^n).

The closer brute forcing gets to normal use, the worse your engineering tradeoffs have to get. But there's no magic number where crypto fails. It just slowly becomes less practical in more situations.

If brute force time is at least the cube of encryption time, you barely have to worry about it being P.

> And the implications for security would be huge because we would have to redefine what we mean by provable security, and then have to make some other arbitrary distinction. Is n^100 secure, but n^99 not?

That doesn't sound right. After all, there's already an arbitrarily smooth continuum between polynomial-time and exponential-time algorithms. See quasipolymomial or sub-exponential algorithms.

Reply on news.ycombinator.com