3 ms·

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

by 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.
- deleted 11y ago
  [deleted]

by Retra 11y ago

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.

deleted 11y ago
[deleted]