Okay, the question of P versus NP is important. Now keep in mind that I admitted this when read the rest below:
Contention: In this research question of P versus NP and in the paper, we are looking at:
(1) A Lot of Hype.
(2) A Search for a Very Long Term Academic Job.
(3) Significant Amounts of Nonsense.
Details:
(1) A Lot of Hype.
(1.A) Nowhere in the article are there any very good explanations that a polynomial algorithm that shows that P = NP would be fast in any practical sense.
Indeed, the article has:
"Technically we could have P = NP, but not have practical algorithms for most NP-complete problems. But suppose in fact we do have very quick algorithms for all these problems."
So, to make such a polynomial algorithm of practical interest, we have to just "suppose" that it will be fast in practical terms.
(1.B) With the "suppose" above, the article has:
"Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface."
No, it's just "scratching" and not "just scratching the surface."
I can absolutely, positively assure all readers that there are plenty of reasonably efficient and powerful means to attack such problems in practice now. In fact, the people flying airplanes, running manufacturing plants, designing large telecommunications networks, etc. are not much interested in attacking these problems with optimization. The main reason is: They just don't want to be bothered. In particular, these problems have long been part of the field of 'operations research', that has long been a dead field, a "late parrot", a dead duck.
Just what is it about people don't want to be bothered that is so difficult for the author of the paper to understand?
(1.C) Solve It All.
The suggestion in the article is that the question of P versus NP is the grand question and, thus, the last big problem in computational complexity.
Let's see: For many of the optimization problems in, say, airline scheduling, manufacturing scheduling, telecommunications network design, given an optimal solution, over the coming few hours, days, or weeks, real world uncertainty commonly will make that solution out of date and far from 'optimal'. So, the real problem that needs to be attacked in practice is optimization over time under uncertainty, and there was no hint of such problems in the paper or that showing that P = NP would provide solutions. Net, it is not clear from the paper that the NP-complete problems cover all the challenges that remain.
A lot of hype.
(2) A Search for a Very Long Term Academic Job.
The paper ends with:
"Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not."
Of course he hopes not: As long as the problem is not solved, a lot of researchers chipping away on apparently quite distant parts continue to have a very stable career!
(3) Significant Amounts of Nonsense.
The article has:
"everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste."
Glad he's interested in "less waste". But, let's see on three points:
(3.A) Approximately Optimal
Commonly in such cost minimization optimization problems now, we report two numbers: First we report the cost of the feasible, but perhaps not optimal, solution we did find. Second we report a lower bound on the cost of an optimal solution. When these two numbers are close for our practical problem, we quit and accept the feasible and approximately optimal solution.
The last time I did this, I had a 0-1 integer linear program with 600,000 variables and 40,013 constraints and found a feasible solution with cost only 0.025% higher than the lower bound, in 905 seconds on a 90 mHz PC.
So, the practical problem is, can we find techniques that get a feasible solution and a lower bound close enough for practice nearly always on the practical problems we face?
Nowhere did the paper recognize this problem or indicate a close connection with the challenge of P versus NP.
Yes, we can ask, given the optimization problem and a cost c, is there a feasible solution with cost less than c? So, since we can check a proposed solution quickly, this is a problem in NP. Then on this problem we can do a binary search on c and converge to optimality. So if this NP problem is in P, then with the binary search our optimal algorithm is also in P.
But it is not clear if this is the same problem as, can we get a feasible solution (in reasonable time, nearly always, on our practical problems) with cost c only 1% higher than a lower bound u? Or only 1% above the cost of an optimal solution (we don't know the cost of an optimal solution).
So, the question P versus NP is much more difficult than demanded by practice.
(3.B) The Big Savings.
The paper has,
"everything will be much more efficient."
This conclusion is unsupported, wildly unjustified, and from experience nonsense. It is not the least bit clear that optimal solutions will on average cost significantly less than the approximately optimal solutions commonly available now.
(3.C) The Cartoon.
Early in the reference,
Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979.
and praised in the paper, is a cartoon with an executive sitting behind a desk, a researcher standing just in front of the desk and stretching behind him over the horizon a long line of researchers, and the researcher explaining to the executive that he, the researcher, can't solve the executive's problem but neither can any of the researchers in the long line because none of them could settle P versus NP.
Nonsense. Made up, junk-think, make-work, prof-scam, busy-work nonsense: The executive's problem was just to save nearly all the money nearly all the time on the real problems, or at least to save some significant money sometimes, and not to guarantee to save all the money, down to the last tiny fraction of one penny, with polynomial computer time, on worst case problems, the worst that can exist even in theory.
Instead the researcher deliberately bamboozled the executive by converting his problem into one the researcher could have an excuse to work on for the rest of his career without getting a solution.
There is one more curious point.
The paper mentioned:
"Consider the traveling salesperson problem again with distances between cities given as the crow flies (Euclidean distance). This problem remains NP-complete but Arora4 gives an efficient algorithm that gets very close to the best possible route."
where his reference is
Arora, S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (Sept. 1998), 753–782.
While I don't know this paper, there is the highly curious,
Richard M. Karp, "The Probabilistic Analysis of Some Combinatorial Search Algorithms," pages 1-19, 'Algorithms and Complexity: New Directions and Recent Results', edited by J. F. Traub, Academic Press, New York, 1976.
So, here's what to do: Given a traveling salesman problem in the plane (or any finite dimensional space) with just Euclidean distances, pick a city, from that city build a minimum spanning tree connecting all the cities (well-known to be polynomial and fast). Then for the traveling salesman tour, just do a depth-first traversal of that tree except do not 'backtrack' in the tree and revisit cities and, instead, just take the direct link to the next city to be visited in the traversal.
Then for cities selected randomly with meager and reasonable assumptions, and as the number of cities n grows, the solutions have distance as close as we please to optimality with probability as high as we please less than 1.
So, for big problems, as long as all we are trying to do is save some travel distance, no problem. For small problems, enumerate!
Broadly, the question of P versus NP does not connect very well with the real needs of optimization in practice.
Ah, never let the real facts get in the way of an exciting story!
What I said is rock solidly true. I hold a Ph.D. in operations research, was Director of Operations research for a major airline, have worked with a good list of some of the best optimization people in the world, and have attacked several challenging combinatorial optimization problems. I've seen people interested and not interested in optimization and concluded with solid evidence that in general, for the problems I mentioned, for optimization, people don't want to be bothered. Here I'm not lacking "imagination" at all. Again, operations research is a dead duck because people don't want to be bothered.
I don't know your field: If you are looking for some 'exact fit' in the sense of, say, the famous NP-complete problem SAT, then the techniques of optimization may be less powerful. But with very different techniques, there has been progress on SAT.
However there is a large body of research with some solid practical power; maybe some of this research would do well for your problems. At least get good with linear programming and, say, C-PLEX. Then look at the old Gilmore-Gomory column generation where the linear program can have many millions of columns, most not even written down yet. Look really hard at nonlinear duality theory -- for a minimization problem, the dual is always maximizing a continuous, concave function! Then look at Lagrangian relaxation. Of course, finish off with branch and bound. Look at the work at Georgia Tech of G. Nemhauser and E. Johnson. Also note: In practice, a large fraction of integer linear programming problems are in fact least cost network flow problems or closely related, and there we can get optimal solutions very quickly and integer optimal solutions for no extra cost. Look at W. Cunningham's work and also D. Bertsekas's. In general, for really large problems, there is a powerful theme: Continuous approximations work well. Your field may not have good knowledge of such work.
Besides, even if what is known is not good for your problems, history shows in solid terms that for progress on your problems, f'get about anything having to do with P versus NP. For getting the solutions you outlined, for years, P versus NP is a fool's errand.
Here I'm giving you good advice in spite of your insult.
I want to live in a P = NP world. Perhaps airline scheduling isn't something to get excited over, but in my field a P = NP world would be the holy grail.
Imagine being able to engineer proteins. ENGINEER PROTEINS. Not just study them or do domain fusions, but to actually be able to design structures to fill a particular need. We could plug into existing metabolic pathways or we could develop entirely novel ones, complete with complex logic circuitry that models interaction with the physical world.
Pollution would be solved. Energy would be solved. Cells would become a new and quite novel form of both computer and machine. A kind that can self-replicate. A kind that we could now feasibly have a compiler for.
Slightly tangent to biotech, consider the computational investigation of all of chemical space. We could quickly and easily discover novel molecular structures and automate their design. We could develop new synthesis reactions and optimize chemical engineering. The products we buy today--think "mundane" things like plastics, or shampoo--could become space age in a matter of years if P = NP.
Too bad this appears to be a different universe I'm describing. In that world all of the "magic" of the computer industry is essentially ported to all of the science fields.
I have some good news for you: For your goals, likely you do not have to wait for P = NP, even if it is true.
Or, for your goals, you do not need the extreme guarantees of P = NP, that is, guaranteed polynomial solutions for ALL your problems in NP, even the worst case that can exist.
Instead, likely you can make nearly all the progress you have in mind with some techniques that just happen to work well for your class of problems. This is what the history shows. That is, people have been doing well solving NP-complete problems well enough for decades without worrying about P versus NP. So, learn some of what has been done, as I outlined and more, and then add to that material in ways important for your problems.
Just MUST realize that the question of P versus NP has been formulated in a way that makes it often shockingly far from getting valuable results in practice. How can this be? Heavily because the P versus NP question concentrates on the worst cases that can exist, and the average cases in practice can be much, MUCH easier.
For more, pay close attention to the Department of Combinatorics and Optimization at Waterloo and Nemhauser's department at Georgia Tech.
Generally it will be tough for me to believe that the field of DNA biology has much knowledge of that material if only because very few people do. Indeed, your desire for P = NP does indicate that your field lets the P versus NP question keep it from going after the field's holy grail, likely for no good reason. Each protein you can correctly fold, each valuable molecule you can create, can be a big step ahead, even without P = NP. Net, f'get about P versus NP.
Next, as I outlined, even if tomorrow someone shows an algorithm that shows P = NP, there is no guarantee that that algorithm will be 'fast'. Instead, something with integer linear programming, touched up with various techniques, might solve nearly all your problems plenty well and be much faster.
Indeed, as in the classic Klee and Minty paper, the simplex algorithm is not polynomial but in practice it totally knocks the socks off the polynomial interior point algorithms. To be more clear, classic simplex runs in 3m where m is the number of constraints and we get to ignore the number of columns. So, classic simplex runs, in practice, faster than a polynomial of degree 1 in the size of the input data. Still, it's 'exponential' in worst case. There are more details on why in a classic paper by K. Borgward.
The polynomial algorithms for linear programming are way too slow for practice.
So, I'm not just blowing smoke here: DO work on your problems but F'GET about P versus NP.
The last paragraph of the article was inspiring. What you say in (2) is nonsense.
Look at it this way: there are lots of examples when someone sought out to solve one problem and ended up solving another or discovering a new problem -- of which is orthogonal to the original problem.
The author was just conveying the field of complexity has grown tremendously from the nature of this problem being so intractable. See Prof. Papadimitriou et al book Combinatorial Complexity as one example that I'm familiar with.
ASIDE: Also for me, I find the discovery of new problems more exhilarating than the solving established problems via new techniques.
What I said in (2) is not nonsense but actually important in the 'sociology' of that field of research: There are people in the field very much hoping that P versus NP will not be resolved so that they can have long lasting jobs, and you would be naive about people and their tactics to say this is "nonsense".
You seem to be forgetting my introduction that I agree that the question of P versus NP is important. The question is good research, and your point is one reason it is.
Note: Although in computing your use of 'orthogonal' is common, a better word choice would be 'independent' or just 'unrelated'.
For you I will try to be still more clear: When I started working on airline scheduling, I talked to a famous mathematician and explained my airline fleet scheduling problem. Right away he said: "NP-complete" and then dismissed my work as hopeless. He was wrong, badly wrong. Airline fleet scheduling can work quite well in practice, thank you. His blurting out "NP-complete" was just a way to dismiss practical problem solving.
For some good public information on airline fleet scheduling, see the work of Ellis Johnson, then at IBM's Yorktown Heights lab, using IBM's Optimization Subroutine Library (OSL), for American Airlines. Ellis understands NP-complete just fine, but he also knows that it's possible in practice to do quite well on the NP-complete problems of real airlines.
Again, our goals in practice do not have to wait for P versus NP. Read again what I wrote about the cartoon.
Umm... I thought it was a pretty good introductory article, listing well-known and uncontroversial stuff. Yes, a polynomial algorithm might not be actually practical. Everybody knows this, and pointing it out every time P=NP comes up is bordering on cliche. Yes, NP-hard combinatorial optimization problems can have easy instances in practice. Why is that a reason for outrage?
Also, the paper was eager to assume that a polynomial algorithm that showed P = NP would be fast and that the world would then get big savings in airlines, manufacturing, etc., and that's nonsense. Generally we can get all but the last pennies of savings now.
Net, the paper is increasing the high confusion about the problem P versus NP.
These claims are false. We can get savings on a small number of "low-hanging fruit" problems, which are easy to approximate on practical instances - bin packing with many small items, scheduling with many short jobs, 2D Euclidean Hamiltonian cycles. What about, for example, the learning applications that Fortnow mentions? Try your C-PLEX on the problem "find the minimal size circuit that explains this big set of observations". You will not get anywhere. There are many other examples.
It makes sense for the industry to concentrate on making a buck out of the easy instances, and leaving the hard stuff to the academics. However, that is different from claiming that hard instances don't exist.
"However, that is different from claiming that hard instances don't exist."
but I didn't claim that there were no hard instances. Again, even showing P = NP does not guarantee to provide a fast algorithm for "hard instances" in NP. Net. the question P versus NP is a bit far from practice.
Again, a big example is the simplex algorithm: In practice, the algorithm finds optimal solutions in about 3m iterations where m is the number of rows, and we get to forget about the number of columns. So in practice simplex is terrific as a 'polynomial' algorithm: It's faster than a degree 1 polynomial since we get to ignore the number of columns. But, simplex, worst case, is exponential. So, there are polynomial algorithms to replace simplex, but they are all far too slow: If simplex takes too long, then the polynomial algorithms take still longer.
Linear programming is one of the best examples we have for where we had an exponential algorithm and found a polynomial one. The result: The polynomial algorithm sucked.
You wrote:
"find the minimal size circuit that explains this big set of observations".
I tried to skip over that part of the paper to keep my response simple.
First it is not clear what he means by "explains", but I fear that I do know. Basically he wants a 'fit', but this is dangerous. In practice, a good approach to finding such fits is classification and regression trees (CART) complete with a book by L. Breiman and others.
But for a 'fit', commonly that's easy: For some positive integer n and, for i = 1, 2, ..., n, we are given real numbers x(i) and y(i). The x(i) are distinct. Now we want a polynomial p of degree n - 1 so that p(x(i)) = y(i). Okay, how to find p? Easy. I leave it as an exercise. Problem is, p doesn't provide much as 'explanation'.
Generally, 'explanation' is tough to get at in part because it tries to get at causality which, just from data, as in the paper, is super tough to get at.
I mentioned C-PLEX for optimization problems. Not all problems in NP are optimization problems. But, curiously, integer linear programming bites off a lot of NP, and C-PLEX with associated techniques is one of the best approaches to integer linear programming.
Contention: In this research question of P versus NP and in the paper, we are looking at:
(1) A Lot of Hype.
(2) A Search for a Very Long Term Academic Job.
(3) Significant Amounts of Nonsense.
Details:
(1) A Lot of Hype.
(1.A) Nowhere in the article are there any very good explanations that a polynomial algorithm that shows that P = NP would be fast in any practical sense.
Indeed, the article has:
"Technically we could have P = NP, but not have practical algorithms for most NP-complete problems. But suppose in fact we do have very quick algorithms for all these problems."
So, to make such a polynomial algorithm of practical interest, we have to just "suppose" that it will be fast in practical terms.
(1.B) With the "suppose" above, the article has:
"Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface."
No, it's just "scratching" and not "just scratching the surface."
I can absolutely, positively assure all readers that there are plenty of reasonably efficient and powerful means to attack such problems in practice now. In fact, the people flying airplanes, running manufacturing plants, designing large telecommunications networks, etc. are not much interested in attacking these problems with optimization. The main reason is: They just don't want to be bothered. In particular, these problems have long been part of the field of 'operations research', that has long been a dead field, a "late parrot", a dead duck.
Just what is it about people don't want to be bothered that is so difficult for the author of the paper to understand?
(1.C) Solve It All.
The suggestion in the article is that the question of P versus NP is the grand question and, thus, the last big problem in computational complexity.
Let's see: For many of the optimization problems in, say, airline scheduling, manufacturing scheduling, telecommunications network design, given an optimal solution, over the coming few hours, days, or weeks, real world uncertainty commonly will make that solution out of date and far from 'optimal'. So, the real problem that needs to be attacked in practice is optimization over time under uncertainty, and there was no hint of such problems in the paper or that showing that P = NP would provide solutions. Net, it is not clear from the paper that the NP-complete problems cover all the challenges that remain.
A lot of hype.
(2) A Search for a Very Long Term Academic Job.
The paper ends with:
"Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not."
Of course he hopes not: As long as the problem is not solved, a lot of researchers chipping away on apparently quite distant parts continue to have a very stable career!
(3) Significant Amounts of Nonsense.
The article has:
"everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste."
Glad he's interested in "less waste". But, let's see on three points:
(3.A) Approximately Optimal
Commonly in such cost minimization optimization problems now, we report two numbers: First we report the cost of the feasible, but perhaps not optimal, solution we did find. Second we report a lower bound on the cost of an optimal solution. When these two numbers are close for our practical problem, we quit and accept the feasible and approximately optimal solution.
The last time I did this, I had a 0-1 integer linear program with 600,000 variables and 40,013 constraints and found a feasible solution with cost only 0.025% higher than the lower bound, in 905 seconds on a 90 mHz PC.
So, the practical problem is, can we find techniques that get a feasible solution and a lower bound close enough for practice nearly always on the practical problems we face?
Nowhere did the paper recognize this problem or indicate a close connection with the challenge of P versus NP.
Yes, we can ask, given the optimization problem and a cost c, is there a feasible solution with cost less than c? So, since we can check a proposed solution quickly, this is a problem in NP. Then on this problem we can do a binary search on c and converge to optimality. So if this NP problem is in P, then with the binary search our optimal algorithm is also in P.
But it is not clear if this is the same problem as, can we get a feasible solution (in reasonable time, nearly always, on our practical problems) with cost c only 1% higher than a lower bound u? Or only 1% above the cost of an optimal solution (we don't know the cost of an optimal solution).
So, the question P versus NP is much more difficult than demanded by practice.
(3.B) The Big Savings.
The paper has,
"everything will be much more efficient."
This conclusion is unsupported, wildly unjustified, and from experience nonsense. It is not the least bit clear that optimal solutions will on average cost significantly less than the approximately optimal solutions commonly available now.
(3.C) The Cartoon.
Early in the reference,
Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979.
and praised in the paper, is a cartoon with an executive sitting behind a desk, a researcher standing just in front of the desk and stretching behind him over the horizon a long line of researchers, and the researcher explaining to the executive that he, the researcher, can't solve the executive's problem but neither can any of the researchers in the long line because none of them could settle P versus NP.
Nonsense. Made up, junk-think, make-work, prof-scam, busy-work nonsense: The executive's problem was just to save nearly all the money nearly all the time on the real problems, or at least to save some significant money sometimes, and not to guarantee to save all the money, down to the last tiny fraction of one penny, with polynomial computer time, on worst case problems, the worst that can exist even in theory.
Instead the researcher deliberately bamboozled the executive by converting his problem into one the researcher could have an excuse to work on for the rest of his career without getting a solution.
There is one more curious point.
The paper mentioned:
"Consider the traveling salesperson problem again with distances between cities given as the crow flies (Euclidean distance). This problem remains NP-complete but Arora4 gives an efficient algorithm that gets very close to the best possible route."
where his reference is
Arora, S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (Sept. 1998), 753–782.
While I don't know this paper, there is the highly curious,
Richard M. Karp, "The Probabilistic Analysis of Some Combinatorial Search Algorithms," pages 1-19, 'Algorithms and Complexity: New Directions and Recent Results', edited by J. F. Traub, Academic Press, New York, 1976.
So, here's what to do: Given a traveling salesman problem in the plane (or any finite dimensional space) with just Euclidean distances, pick a city, from that city build a minimum spanning tree connecting all the cities (well-known to be polynomial and fast). Then for the traveling salesman tour, just do a depth-first traversal of that tree except do not 'backtrack' in the tree and revisit cities and, instead, just take the direct link to the next city to be visited in the traversal.
Then for cities selected randomly with meager and reasonable assumptions, and as the number of cities n grows, the solutions have distance as close as we please to optimality with probability as high as we please less than 1.
So, for big problems, as long as all we are trying to do is save some travel distance, no problem. For small problems, enumerate!
Broadly, the question of P versus NP does not connect very well with the real needs of optimization in practice.
Ah, never let the real facts get in the way of an exciting story!