4 ms·

To start, yes, I do like the question of P versus NP and regard it as a very important research question. My reaction to the video lecture: Wow. Amazing. Gee

by graycat 11y ago

To start, yes, I do like the question of P versus NP and regard it as a very important research question. My reaction to the video lecture: Wow. Amazing. Gee whiz. P versus NP. What a biggie! Or is it? There does seem to be a little, tiny, itsy, bitsy point where the lecture went off the track: The lecture gave a big list of some of the amazing things we could do if we could prove that P = NP. Some of the items on that list were protein folding (to cure cancer) and scheduling. Right? Not so much: If someone has an important problem in scheduling, protein folding or any of the NP-complete problems, bring forward that actual, specific, instance of the real problem. Why? Because there's no proof and little evidence that finding a solution will be too difficult for "current computers". To this claim I can hear the complaint now: "But, but, but, the problems in NP-complete are too difficult to solve for current computers because as the problem size increases, the best known algorithms have running time that grows as an exponential in the size of the problem, and exponential growth limits us to problem instances of just small down to tiny size." Yup, can hear that complaint. Good news, guys: The complaint is false and does not correctly explain the challenge of NP-complete. E.g,, 0-1 integer linear programming is in NP-complete, but I can write down, as fast as I can type, such problems about as big as you please that I, or anyone, can solve quickly just by simple inspection. It's true. E.g., for any positive integer n, consider the 0-1 integer linear programming problem max z = 1 * x1 + 2 * x2 + ... + n * xn subject to x1 + x2 + ... + xn = 1 x1, x2, ..., xn = 0 or 1 So, the error in the complaint is that actually the question of P versus NP has to do with worst case instances of the problems. But practical instances are not all worst case, and for many of the practical instances we can get solutions. So, for any particular actual, specific, instance of a real problem, bring it forward -- you might be able to get a solution. And, wait, there's more! For a problem like scheduling, mostly what is desired is just to save money in the actual operations, say, airlines where we need to schedule the planes for the planned flights, the crews, and maintenance for the planes. Since the planes do fly, tough to convince me that the scheduling is impossible. So, if spending $200 million a month on operations, an optimal schedule could save $20 million, can find a schedule that is approximately optimal and saves all but the last $100,000, then take the $19,900,000 savings and be happy. The claim "we want to show that P = NP so that we can solve all these important problems" has been going on since the cartoon early in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness'. where the mathematician stood before the business executive and admitted that he could not solve the executive's problem but neither could any of the mathematicians in a long line. Likely nonsense: The mathematician was likely just looking for a long term job and actually not at all interested in solving the executive's problem. Why? Because there was no indication that the executive's problem was large and worst case and needed an exactly optimal solution instead of a nearly optimal solution. The executive's problem might have been relatively easy to solve, with a nearly optimal solution and maybe with an exactly optimal solution. Indeed, the book was from Bell Labs where one of their interests was network design. Well, since the phones did work, somehow Bell did find feasible solutions. Optimal? Maybe not. So, what was "the executive's problem" that was in NP-complete and "too difficult to solve?". Maybe he just wanted to design a telecommunications network to have the needed performance and reliability and, otherwise, get the cost down as much as possible or nearly so. Finding an algorithm that shows that P = NP is very likely a significantly different problem, not his problem, and not necessary for his problem. This erroneous belief that all large instances of problems in NP-complete are too difficult to solve is too common: E.g., once I got a problem in allocation of marketing resources. The instance was 0-1 integer linear programming with 40,000 constraints and 600,000 variables. I thought for a day or so, typed in some software, did some Lagrangian relaxation, and in 905 seconds on a 90 MHz PC got a feasible solution guaranteed to be within 0.025% of optimality. Close enough for gumment work! Then, later, as I was considering network design for the Internet, I got an interview at a network design startup in Texas and mentioned the problem with the 600,000 variables. Well, the whole technical staff was on the other side of the table, had heard the horror stories about NP-complete in college, and concluded to a person that I was claiming to have done the impossible and had to be lying. I left without a job offer, and they soon went out of business. By the way, Mother Nature does protein folding, right? Hmm ....

Retra 11y ago
What is your point? That if we were all totally satisfied with half-ass solutions and non-answers, we wouldn't have to worry P = NP? >By the way, Mother Nature does protein folding, right? Yes, but it does it directly without simulating any models of itself. As soon as you add the indirection and abstraction needed for human communication, you can't use those methods. That's like saying "Usain Bolt can run fast, so you should be able to run fast just by pretending to be him." You can't be nature by pretending to act like it in an abstract model. I can't solve a protein folding problem by simply realizing that my body already folds proteins. That has nothing to do with the mental models of protein folding we use.
- graycat 11y ago
  > What is your point? That if we were all totally satisfied with half-ass solutions and non-answers, we wouldn't have to worry P = NP? No. My point is that the video clip claimed too much for the importance in practice of finding an algorithm that shows that P = NP. Here the video clip was wrong. In particular, the video clip mentioned scheduling problems. Yes, they are important. But as in my scenario, if, say, in airline scheduling where we are spending $200 million now, an optimal solution could save $20 million, and we can get a solution that will save all but the last $100,000, then we should take the savings of $19,900,000 and be happy. And, a solution that saves $19,900,000, saves nearly 10% of the $200 million, saves all but the last $100,000, saves all but that last 0.05% of the $200 million is, from the point of view of the airline, not at all "half-ass". Or, if we are going to say that the research question of P versus NP is important for scheduling, which the video clip does, then we have to accept the clear, blunt fact that what is really important in scheduling is just saving money, and saving all but the last 0.05% is essentially just what the heck we really want. The reason the clip was wrong is that much of the challenge of the question of P versus NP is the focus on worst case problems, but not nearly all practical instances of problems in NP-complete are worst case. So, for important practical problems, e.g., 0-1 integer linear programming, we've known for several decades that often in practice we can get optimal solutions. E.g., in less than a minute at Google I found at http://www.wired.com/2013/01/traveling-salesman-problem/ http://www.wired.com/2013/01/traveling-salesman-problem/ "The shortest traveling salesman route going through all 13,509 cities in the United States with a population of at least 500 (as of 1998)." In my experience, it's been the case for decades that a surprisingly large fraction of applied mathematicians working on optimization of problems in NP-complete are overly focused, nearly obsessive, with nearly religious fervor, over getting solutions that are optimal, down to the last tiny fraction of the last penny, always and rejecting anything else as sloppy, irresponsible, immoral or some such, maybe "half ass". This really was the attitude in the cartoon early in Garey and Johnson. Yes, it was darned nice to have heap sort: From the Gleason bound, for positive integer n, to sort n items by comparing pairs, can't run faster than O( n ln(n) ). Then, in both average case and worst case, heap sort does this. Nice. Super nice. Call a heap sort routine and know that will get O( n ln(n) ) performance, no ifs, ands, or buts about it. So, sure, worst case guarantees are nice to have. Always necessary? No. Nice? Yes. At one point there was a problem of assigning anti-ballistic missiles to incoming warheads, and it would be really nice to have an algorithm with guaranteed polynomial worst case performance. Well, can attack that problem with least cost network flows and attack that with the network version of the simplex algorithm of linear programming. With a modification for strongly feasible bases, can be sure that the algorithm will not cycle. But do we have a polynomial worst case guarantee? Apparently not. But there is an algorithm for that assignment problem with such a guarantee. Apparently the main name is D. Bertsekas, long at MIT. Nice work. And for solving the optimization problems in NP-complete, again it would be really nice to have an algorithm that is fast and polynomial on worst case problems. Solid gold, diamond encrusted algorithm. Nice? Yes. Doable now? No. Necessary in practice? Often no. So, we don't have our dream solid gold, diamond encrusted algorithm. The video clip is essentially claiming that we need a solid gold diamond encrusted algorithm to solve practical scheduling problems. This claim is claiming too much and is false. Gee, this is like claiming that because we don't have a Rolls Royce we can't take our old Chevy to the grocery store. Nope: Sure, it might be nice to have a Rolls, but in the meanwhile we are hungry, need to get to the grocery store, and our old Chevy will do just fine. The video clip is saying that because we don't have our dream solid gold solution, we have to go hungry until we show P = NP. Nonsense. Again, this nonsense has been going on for decades, all the way back to the cartoon in Garey and Johnson, the cartoon that claimed that no mathematician could solve the executive's problem. Likely nonsense: Maybe true if bend way over backwards to make in practice an absurd rewrite of the executive's problem as to have a guarantee to save the very last tiny fraction of the last penny, with a polynomial algorithm, on the worst case problems that can exist -- the executive likely doesn't give even a drop of coffee for that very last tiny fraction of one penny, likely does not have worst case problems, and for his problem sizes doesn't necessarily need a polynomial algorithm. The cartoon was wacko. Scheduling and many other problems in NP-complete are darned important in practice. E.g., saving that $19,900,000 is darned important. The video clip is saying that need to get the very last tiny fraction of the last penny of savings on arbitrarily large, worst case problems and, thus, need to show that P = NP. Wrong: The real importance of the scheduling problem is to save the first $19,900,000 and not the last $100,000. And there is no moral shame in leaving the last $100,000, 0.05%, not saved. My point here is totally simple, clear, and obvious. Just why too much of the relevant applied math community wants to take the erroneous position of the video clip or the cartoon in Garey and Johnson, essentially be moralistic about the last 0.05% and optimality, is beyond me. Yes, in some early texts in operations research, optimality was taken as essentially a moral absolute. My remark that nature solves protein folding problems quickly and routinely was to address a possible philosophical question: Is it possible in this universe to construct a machine that can solve large protein folding problems quickly or are such problems so challenging that somehow they are beyond this universe? Well, the problems are not beyond this universe, and likely nearly any animal, life form, or even virus is an example of a machine that does solve such problems. So, such a machine really is possible. So, more specifically, if protein folding is in NP-complete, then maybe actually P = NP -- which would surprise many researchers in that field.

by graycat 11y ago

Retra 11y ago

What is your point? That if we were all totally satisfied with half-ass solutions and non-answers, we wouldn't have to worry P = NP? >By the way, Mother Nature does protein folding, right? Yes, but it does it directly without simulating any models of itself. As soon as you add the indirection and abstraction needed for human communication, you can't use those methods. That's like saying "Usain Bolt can run fast, so you should be able to run fast just by pretending to be him." You can't be nature by pretending to act like it in an abstract model. I can't solve a protein folding problem by simply realizing that my body already folds proteins. That has nothing to do with the mental models of protein folding we use.

graycat 11y ago
> What is your point? That if we were all totally satisfied with half-ass solutions and non-answers, we wouldn't have to worry P = NP? No. My point is that the video clip claimed too much for the importance in practice of finding an algorithm that shows that P = NP. Here the video clip was wrong. In particular, the video clip mentioned scheduling problems. Yes, they are important. But as in my scenario, if, say, in airline scheduling where we are spending $200 million now, an optimal solution could save $20 million, and we can get a solution that will save all but the last $100,000, then we should take the savings of $19,900,000 and be happy. And, a solution that saves $19,900,000, saves nearly 10% of the $200 million, saves all but the last $100,000, saves all but that last 0.05% of the $200 million is, from the point of view of the airline, not at all "half-ass". Or, if we are going to say that the research question of P versus NP is important for scheduling, which the video clip does, then we have to accept the clear, blunt fact that what is really important in scheduling is just saving money, and saving all but the last 0.05% is essentially just what the heck we really want. The reason the clip was wrong is that much of the challenge of the question of P versus NP is the focus on worst case problems, but not nearly all practical instances of problems in NP-complete are worst case. So, for important practical problems, e.g., 0-1 integer linear programming, we've known for several decades that often in practice we can get optimal solutions. E.g., in less than a minute at Google I found at http://www.wired.com/2013/01/traveling-salesman-problem/ http://www.wired.com/2013/01/traveling-salesman-problem/ "The shortest traveling salesman route going through all 13,509 cities in the United States with a population of at least 500 (as of 1998)." In my experience, it's been the case for decades that a surprisingly large fraction of applied mathematicians working on optimization of problems in NP-complete are overly focused, nearly obsessive, with nearly religious fervor, over getting solutions that are optimal, down to the last tiny fraction of the last penny, always and rejecting anything else as sloppy, irresponsible, immoral or some such, maybe "half ass". This really was the attitude in the cartoon early in Garey and Johnson. Yes, it was darned nice to have heap sort: From the Gleason bound, for positive integer n, to sort n items by comparing pairs, can't run faster than O( n ln(n) ). Then, in both average case and worst case, heap sort does this. Nice. Super nice. Call a heap sort routine and know that will get O( n ln(n) ) performance, no ifs, ands, or buts about it. So, sure, worst case guarantees are nice to have. Always necessary? No. Nice? Yes. At one point there was a problem of assigning anti-ballistic missiles to incoming warheads, and it would be really nice to have an algorithm with guaranteed polynomial worst case performance. Well, can attack that problem with least cost network flows and attack that with the network version of the simplex algorithm of linear programming. With a modification for strongly feasible bases, can be sure that the algorithm will not cycle. But do we have a polynomial worst case guarantee? Apparently not. But there is an algorithm for that assignment problem with such a guarantee. Apparently the main name is D. Bertsekas, long at MIT. Nice work. And for solving the optimization problems in NP-complete, again it would be really nice to have an algorithm that is fast and polynomial on worst case problems. Solid gold, diamond encrusted algorithm. Nice? Yes. Doable now? No. Necessary in practice? Often no. So, we don't have our dream solid gold, diamond encrusted algorithm. The video clip is essentially claiming that we need a solid gold diamond encrusted algorithm to solve practical scheduling problems. This claim is claiming too much and is false. Gee, this is like claiming that because we don't have a Rolls Royce we can't take our old Chevy to the grocery store. Nope: Sure, it might be nice to have a Rolls, but in the meanwhile we are hungry, need to get to the grocery store, and our old Chevy will do just fine. The video clip is saying that because we don't have our dream solid gold solution, we have to go hungry until we show P = NP. Nonsense. Again, this nonsense has been going on for decades, all the way back to the cartoon in Garey and Johnson, the cartoon that claimed that no mathematician could solve the executive's problem. Likely nonsense: Maybe true if bend way over backwards to make in practice an absurd rewrite of the executive's problem as to have a guarantee to save the very last tiny fraction of the last penny, with a polynomial algorithm, on the worst case problems that can exist -- the executive likely doesn't give even a drop of coffee for that very last tiny fraction of one penny, likely does not have worst case problems, and for his problem sizes doesn't necessarily need a polynomial algorithm. The cartoon was wacko. Scheduling and many other problems in NP-complete are darned important in practice. E.g., saving that $19,900,000 is darned important. The video clip is saying that need to get the very last tiny fraction of the last penny of savings on arbitrarily large, worst case problems and, thus, need to show that P = NP. Wrong: The real importance of the scheduling problem is to save the first $19,900,000 and not the last $100,000. And there is no moral shame in leaving the last $100,000, 0.05%, not saved. My point here is totally simple, clear, and obvious. Just why too much of the relevant applied math community wants to take the erroneous position of the video clip or the cartoon in Garey and Johnson, essentially be moralistic about the last 0.05% and optimality, is beyond me. Yes, in some early texts in operations research, optimality was taken as essentially a moral absolute. My remark that nature solves protein folding problems quickly and routinely was to address a possible philosophical question: Is it possible in this universe to construct a machine that can solve large protein folding problems quickly or are such problems so challenging that somehow they are beyond this universe? Well, the problems are not beyond this universe, and likely nearly any animal, life form, or even virus is an example of a machine that does solve such problems. So, such a machine really is possible. So, more specifically, if protein folding is in NP-complete, then maybe actually P = NP -- which would surprise many researchers in that field.