P vs. NP: An Assumption That Runs the Internet

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.

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.

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.

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.

For those in the same position as I, https://en.wikipedia.org/wiki/Polynomial_hierarchy may be a good start.

[1] http://www.imdb.com/title/tt1801123/?ref_=fn_al_tt_7

> The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete. ( https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co... )

The author got this wrong in the article -- just because you can check that each house has been visited in polynomial time proves nothing.

it's like this: if I give you a large number and say "factor this", you will work hard figuring out the answer, but if I give you a set of factors and say multiply them together and see if they equal the big number, you can do that fairly quickly. i.e. you can check the answer a lot easier than you can find the answer.

An NP complete optimal routing problem is the same way, it's hard to find an answer, but if somebody gives you the optimal solution, it is easy to check that it is optimal by substituting segments from the solution set for segments that are not in the solution set, and trying to incrementally improve on it: if you have a solution, none of your substitutions will piece-wise be an improvement, furthermore, you can do it in an orderly way that "proves" your route is best precisely without duplicating all your work. This is the part I don't remember but it's something like "find the longest segment on your route, is there some shorter way to accomplish what that accomplishes? no there isn't. or look at the shortest segments, are they penny-wise but pound-foolish, no they aren't." i.e. the part I do remember is that it is polynomial time to confirm the answer, and it is not polynomial time to find the answer. This is what is in fact meant by "non-deterministic polynomial", it's polynomial only if you magically know the answer in a non-deterministic way. Polynomial to check, but in a deterministic way it is not polynomial to determine.

Again, sorry for all the handwaving, but I'm pretty certain that's right.

Oh, and while I'm here, what was the most irritating thing about this article is that P vs NP is not a huge "assumption". Call it a conjecture, call it a hypothesis, call it a problem to solve, but it's not an assumption, it's been tested long and hard by a lot of really smart people and it's the fringes of our knowledge. That's not what is typically meant by the word "assumption".

It is easy to prove if such a tour exists: simply give me tour. I can sum up the lengths and check that the sum < L. Finding such a tour is the computationally hard part in the worst of cases.