3 ms·

Nice interview: Nice clarity on quantum computing and P versus NP.

by graycat 11y ago

enriquto 11y ago
But be careful, his interpretation of P versus NP is rather light-hearted (but OK, given that it's not his speciality). He says: 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 n1000 time or anything silly like that)—then all cryptographic codes that depend on the adversary having limited computing power would be broken. But the parenthetical remark is not a negligible detail. The class P contains those O(n^1000) algorithms, and also much, much slower ones. Being in P does not mean at all "efficient". This is one of the reasons why many people (e.g. Knuth) say that P=NP is not crazy. The class P is so huge, that it must certainly contain extremely clever algorithms that reduce NP to P. Yet, there are may be no practical implications of this equality.
- graycat 11y ago
  Yes. So far nearly all our famous algorithms run in ln(n), n, ln(n)n, or n^2. So, we don't have much experience with algorithms that run in n^1000 or insight into what such algorithms might do. On the other hand, too commonly when we can't find an algorithm that runs in, say, n^2 or faster, we do have algorithms that run in 2^n. So, we suspect that there is something fundamental about exponential and fundamentally weak about polynomial. But as you point out, that is just something we detect sniffing with our nose. The point where I critique the P versus NP issue is the claim, implicit or explicit, that if we have a practical instance of a problem in NP-complete, then that instance has to be too hard to solve in practice. Not necessarily so: Many particular instances of an NP-complete problem, even with what appear for practice to be quite large values of n, might be fairly easy to solve. E.g., for an instance of the knapsack problem (IIRC in NP-complete), attack with a cute version of dynamic programming. For 0-1 a practical instance of integer linear programming (in NP-complete), attack with the simplex algorithm, maybe branch and bound, maybe Lagrangian relaxation, etc. And, a related issue for practice, in some optimization problems, the goal is to save money. So, in practice it can be fairly easy to save the first 15% of everything that is being spent and save all but that last $0.01 that can be saved even in theory (that is, come within a penny of optimality) and a total pain to save that last penny and know that we have done so. The OP said that if we have an algorithm that shows P = NP, then for each of the other Clay Math problems, say, problem X, and for positive integer n, we can ask: Is there a string of n or fewer characters that, in the sense of Whitehead and Russell, is a proof of problem X and let our P = NP algorithm answer that. Well, we'd be super happy for just anything that would give us such an answer for just one case of problem X and just a realistic value of n and to heck with the general case. More generally that is, the theory of NP-complete concentrates on worst case instances of problems, and not all real instances are worst case or nearly so. So, for the practical instances of problems in NP-complete that we can solve, exactly or close enough to save nearly all the money, just do so, take the money to the bank, and be happy. Then, sadly, we have to notice that currently in practice there is surprisingly little interest in such problems and solutions. Heck, someone could take a collection of the current, routine software for solving instances of problems in NP-complete, advertise (falsely) that they have an algorithm that shows that P = NP and also have corresponding software, run their software in the cloud, invite people to submit problems, and charge big bucks for solutions. Then, get paid for the practical instances their old, routine algorithms do solve and make some excuse for the rest -- money back guarantee. Problem is, I doubt that very many people much care. Why do I suspect that people don't care? Because I've see several important practical cases, and there people didn't much care. But, I confess, there is a lot of misunderstanding out there. E.g., once I was talking with some people who needed to solve, exactly, although approximately would be good, too, a lot of instances of some 0-1 integer linear programming problems (definitely in NP-complete). So I explained that I had recently solved an instance of a 0-1 integer linear programming that had 40,000 constraints and 600,000 variables. My solution was in 905 seconds on a 90 MHz PC, and the feasible solution found was within 0.025% of optimality and might have been optimal. The people I was talking to were happy? Nope: They had been told about the difficulty of the NP-complete problems, heard the big numbers 40,000 and 600,000, and concluded that I had to be lying. I wasn't lying. It's just that, while 0-1 integer linear programming is in NP-complete, not all instances of large 0-1 integer linear programming problems are difficult to solve; instead, in practice, a lot of instances are quite reasonable to solve exactly or plenty close enough for essentially everything of interest in practice. Right, 0-1 with 600,000 variables, so for total enumeration we're looking at 2^600,000. Gotta be impossible, right? Nope. Instead it was fairly easy. So, it boils down that the question of P versus NP is, say, except for the $1 million Clay prize, a pure math question heavily of long term philosophical interest instead of an engineering problem of current practical interest. For current practical interest, we should be attacking practical instances of problems which with current algorithms, software, and computing we can often do quite well.

Nice interview: Nice clarity on quantum computing and P versus NP.

by graycat 11y ago

Nice interview: Nice clarity on quantum computing and P versus NP.

But be careful, his interpretation of P versus NP is rather light-hearted (but OK, given that it's not his speciality). He says: 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 n1000 time or anything silly like that)—then all cryptographic codes that depend on the adversary having limited computing power would be broken. But the parenthetical remark is not a negligible detail. The class P contains those O(n^1000) algorithms, and also much, much slower ones. Being in P does not mean at all "efficient". This is one of the reasons why many people (e.g. Knuth) say that P=NP is not crazy. The class P is so huge, that it must certainly contain extremely clever algorithms that reduce NP to P. Yet, there are may be no practical implications of this equality.

graycat 11y ago
Yes. So far nearly all our famous algorithms run in ln(n), n, ln(n)n, or n^2. So, we don't have much experience with algorithms that run in n^1000 or insight into what such algorithms might do. On the other hand, too commonly when we can't find an algorithm that runs in, say, n^2 or faster, we do have algorithms that run in 2^n. So, we suspect that there is something fundamental about exponential and fundamentally weak about polynomial. But as you point out, that is just something we detect sniffing with our nose. The point where I critique the P versus NP issue is the claim, implicit or explicit, that if we have a practical instance of a problem in NP-complete, then that instance has to be too hard to solve in practice. Not necessarily so: Many particular instances of an NP-complete problem, even with what appear for practice to be quite large values of n, might be fairly easy to solve. E.g., for an instance of the knapsack problem (IIRC in NP-complete), attack with a cute version of dynamic programming. For 0-1 a practical instance of integer linear programming (in NP-complete), attack with the simplex algorithm, maybe branch and bound, maybe Lagrangian relaxation, etc. And, a related issue for practice, in some optimization problems, the goal is to save money. So, in practice it can be fairly easy to save the first 15% of everything that is being spent and save all but that last $0.01 that can be saved even in theory (that is, come within a penny of optimality) and a total pain to save that last penny and know that we have done so. The OP said that if we have an algorithm that shows P = NP, then for each of the other Clay Math problems, say, problem X, and for positive integer n, we can ask: Is there a string of n or fewer characters that, in the sense of Whitehead and Russell, is a proof of problem X and let our P = NP algorithm answer that. Well, we'd be super happy for just anything that would give us such an answer for just one case of problem X and just a realistic value of n and to heck with the general case. More generally that is, the theory of NP-complete concentrates on worst case instances of problems, and not all real instances are worst case or nearly so. So, for the practical instances of problems in NP-complete that we can solve, exactly or close enough to save nearly all the money, just do so, take the money to the bank, and be happy. Then, sadly, we have to notice that currently in practice there is surprisingly little interest in such problems and solutions. Heck, someone could take a collection of the current, routine software for solving instances of problems in NP-complete, advertise (falsely) that they have an algorithm that shows that P = NP and also have corresponding software, run their software in the cloud, invite people to submit problems, and charge big bucks for solutions. Then, get paid for the practical instances their old, routine algorithms do solve and make some excuse for the rest -- money back guarantee. Problem is, I doubt that very many people much care. Why do I suspect that people don't care? Because I've see several important practical cases, and there people didn't much care. But, I confess, there is a lot of misunderstanding out there. E.g., once I was talking with some people who needed to solve, exactly, although approximately would be good, too, a lot of instances of some 0-1 integer linear programming problems (definitely in NP-complete). So I explained that I had recently solved an instance of a 0-1 integer linear programming that had 40,000 constraints and 600,000 variables. My solution was in 905 seconds on a 90 MHz PC, and the feasible solution found was within 0.025% of optimality and might have been optimal. The people I was talking to were happy? Nope: They had been told about the difficulty of the NP-complete problems, heard the big numbers 40,000 and 600,000, and concluded that I had to be lying. I wasn't lying. It's just that, while 0-1 integer linear programming is in NP-complete, not all instances of large 0-1 integer linear programming problems are difficult to solve; instead, in practice, a lot of instances are quite reasonable to solve exactly or plenty close enough for essentially everything of interest in practice. Right, 0-1 with 600,000 variables, so for total enumeration we're looking at 2^600,000. Gotta be impossible, right? Nope. Instead it was fairly easy. So, it boils down that the question of P versus NP is, say, except for the $1 million Clay prize, a pure math question heavily of long term philosophical interest instead of an engineering problem of current practical interest. For current practical interest, we should be attacking practical instances of problems which with current algorithms, software, and computing we can often do quite well.