5 ms·

"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 cu

"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." Moreover, while the most obvious way of proving P = NP would be to find a P solution to an NP-complete problem, it's possible that someone will show existence of such a solution without being able to identify the particular solution. In that case, we don't get to do anything we couldn't do before. It's also possible that we'll find a solution to an NP-complete problem that's O(n^million). That's in P, but may be substantially more out of reach than our O(2^n) approaches on realistically sized problems.

graycat 11y ago
While I don't know the latest research results on the question of P versus NP, it's long been easy to guess that a polynomial algorithm with a high degree polynomial, say, your million, would on most real problem instances be as much of a challenge as an exponential algorithm. But my post was not really about your "way of proving P = NP". Instead I was considering the statement in the video that showing P = NP is important because it would let us make progress on protein folding (for curing cancer), scheduling, etc. I object to that statement because for a significant fraction of such problem instances, including some impressively large, we have a significantly good chance of getting solutions now and do not have to wait for more research on P versus NP. My point, then, was, if someone has some actual problems in protein folding, scheduling, and other NP-complete problems, likely they do not have to wait for an algorithm that shows P = NP. Instead there's a significant chance that current algorithms, software, and computers can solve their problem instances. Again, NP-complete problems of size n clearly are too challenging for "current computers" for exact solutions to worst case problems with large n. Here note the worst case. Instead, and as I illustrated, there are instances of NP-complete problems, e.g., 0-1 integer linear programming, where it is quite routine to find optimal solutions to real problem instances with impressively large n. Important names for such work include G. Nemhauser, E. Johnson, R. Bixby. That is, the field of operations research has been attacking and solving important, practical instances of problems in NP-complete for several decades. Again, if there are some important instances of some NP-complete problems, then don't have to wait for P = NP and, instead, should bring the problems forward now -- solutions may be reasonably easy to find now. That is, where the video clip was essentially claiming that to solve problems in protein folding, scheduling, etc., we have to wait for a proof showing P = NP was wrong -- for optimal solutions to worst case instances of large problems, we have to wait, but not all practical instances are worst case, and sometimes we are quite happy with nearly optimal solutions.
- dllthomas 11y ago
  I got your point, and I wasn't disagreeing with you; I was expanding on what you said along the axis of "... and here are some other ways in which we might learn P = NP and have that solve nothing for us."

graycat 11y ago

While I don't know the latest research results on the question of P versus NP, it's long been easy to guess that a polynomial algorithm with a high degree polynomial, say, your million, would on most real problem instances be as much of a challenge as an exponential algorithm. But my post was not really about your "way of proving P = NP". Instead I was considering the statement in the video that showing P = NP is important because it would let us make progress on protein folding (for curing cancer), scheduling, etc. I object to that statement because for a significant fraction of such problem instances, including some impressively large, we have a significantly good chance of getting solutions now and do not have to wait for more research on P versus NP. My point, then, was, if someone has some actual problems in protein folding, scheduling, and other NP-complete problems, likely they do not have to wait for an algorithm that shows P = NP. Instead there's a significant chance that current algorithms, software, and computers can solve their problem instances. Again, NP-complete problems of size n clearly are too challenging for "current computers" for exact solutions to worst case problems with large n. Here note the worst case. Instead, and as I illustrated, there are instances of NP-complete problems, e.g., 0-1 integer linear programming, where it is quite routine to find optimal solutions to real problem instances with impressively large n. Important names for such work include G. Nemhauser, E. Johnson, R. Bixby. That is, the field of operations research has been attacking and solving important, practical instances of problems in NP-complete for several decades. Again, if there are some important instances of some NP-complete problems, then don't have to wait for P = NP and, instead, should bring the problems forward now -- solutions may be reasonably easy to find now. That is, where the video clip was essentially claiming that to solve problems in protein folding, scheduling, etc., we have to wait for a proof showing P = NP was wrong -- for optimal solutions to worst case instances of large problems, we have to wait, but not all practical instances are worst case, and sometimes we are quite happy with nearly optimal solutions.

dllthomas 11y ago
I got your point, and I wasn't disagreeing with you; I was expanding on what you said along the axis of "... and here are some other ways in which we might learn P = NP and have that solve nothing for us."