This article seems to assume that problems in P are computable no matter the size. If it is shown NP=P, but the best algorithm we have is O(n^100), we still don't have a computer that can actually finish the computation.
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.
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."
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.
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.
"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.
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...
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.
> If P equals NP, then you could solve anything as easily as you could verify it.
This is the core oversimplification of the article—if P=NP there's no guarantee that the solution is as easy as the verification. O(n^3) is still more expensive than O(n^2), even though both are in P.
I don't understand how verifying a TSP is any different to solving it - I.e. don't I have to do just as much work to verify that a particular solution is correct as if I was solving it from scratch? I.e. brute force?
The Traveling Salesman Decision Problem, the one that's NP-complete and not just NP-hard, does not ask for the lowest cost route. It asks whether there is a route cheaper than k. Verifying that is trivial, you just follow the route and compare to k.
The actual decision problem statement for TSP is "Does there exist a tour of less than length L".
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.
TSP is NP-hard -- we don't know if it's in NP (that is, we don't even know if there's a polynomial time algorithm to verify whether a proposed solution is optimal). The decision problem of TSP is NP-complete:
> 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.
There are a few ways to ask the TSP question. One question is "give me the shortest route geometry", this problem is NP-hard and can't be verified easily, this is what you're thinking of. However, the decision version of the problem is usually phrased "Is there a tour of less than length L", and this is NP-Complete - takes a while to find the tour, but it's trivial to check if it's less than length L.
That works for one way (where the tour exists), however, if the true answer to the particular decision problem is "no! it can't be done in L steps!" - then the only way to verify is to repeat the whole process, no?
Having an easily verifiable tour that does it in L+1 doesn't really help in verification that some other combination could or could not do it in L steps.
NP only requires that you can verify a positive answer in polynomial time. Problems with polynomial time proofs for negative answers form the class Co-NP.
Besides that, if you can solve the decision problem and the distances are well-behaved, for example integers, you can solve the other variants, you can perform a binary search for the minimal tour length and you can find the actual tour by probing all edges, i.e. removing one by one and checking whether that increases the minimal tour length.
You can just choose an arbitrary starting L, and if the answer is No, keep doubling your guess until the answer is Yes, then just binary search from there. Or if you want to start with the maximum possible L, just start with the sum of all the edge weights in the graph.
(other people have answered you already, and their answers seem quite knowledgeable, but I sense their answers are actually off the point of your question, i.e. I think there is a better answer than you have been given. However, I learned this material long time ago and the precise answer is not fresh in my mind, so hopefully I can give you the gist, we'll see, but apologies in advance for all my hand waving)
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".
When ever I see P != NP around, it reminds me of when a matrix is equal to its self adjoint, and I wonder if you use any predefined curves and treat it as a polynomial eigenvalue problem, then project it onto a lower dimensional complex space, if one can then use the solutions to generate approximately the observed ciphertext?
There is no need for the optimal. E.g. you can solve most routing problems with >95% efficiency using heuristics with O(1) or O(log n) asymptotic time complexity.
Sure, but that is kind of beside the point. For most problems where the distinction between P and NP is important, the biggest being encryption, "95% efficiency" is absolutely useless.
Until a "95% efficiency" heuristic/approximation can be applied to a primality test, in that case (e.g. if someone finds a geometric heuristic for primality).
Routing is not the same as the Traveling Salesman problem unless you want your packets to go thru all the routers. It's a shortest path problem, which is P.
P == NP does not really mean that solving is as easy is verifying the solution. The former could be O(n^4) while the latter O(1). It rather means that if a solution can be verified in a reasonable time (polinomial), then it was also possible to calculate it in a reasonable time.
45 comments
[ 3.3 ms ] story [ 85.0 ms ] threadAlso 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.
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.
"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
His main point, which is more about the practical effects of P=NP is much more convincing, and actually very common I believe.
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.
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-...
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...
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).
Of course, if we discover that P=NP, getting at those lower bounds would be a priority...
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.
This is the core oversimplification of the article—if P=NP there's no guarantee that the solution is as easy as the verification. O(n^3) is still more expensive than O(n^2), even though both are in P.
http://www.scottaaronson.com/writings/phcollapse.pdf
For those in the same position as I, https://en.wikipedia.org/wiki/Polynomial_hierarchy may be a good start.
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.
> 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.
Having an easily verifiable tour that does it in L+1 doesn't really help in verification that some other combination could or could not do it in L steps.
Besides that, if you can solve the decision problem and the distances are well-behaved, for example integers, you can solve the other variants, you can perform a binary search for the minimal tour length and you can find the actual tour by probing all edges, i.e. removing one by one and checking whether that increases the minimal tour length.
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".
[1] http://www.imdb.com/title/tt1801123/?ref_=fn_al_tt_7
P == NP does not really mean that solving is as easy is verifying the solution. The former could be O(n^4) while the latter O(1). It rather means that if a solution can be verified in a reasonable time (polinomial), then it was also possible to calculate it in a reasonable time.