P vs. NP and the Computational Complexity Zoo (2014) [video]

The decision version of TSP would be formulated as: Given a complete graph G and a budget b, decide if there exists a path that visits each node and has cumulative weight less than b.

If you have a solver for decision TSP, then you can solve the optimization version of TSP by performing binary search on the budget b.

I'm glossing over some details, but there's a clearer explanation on how to solve search problems with an oracle for decision problems in Sipser.

Traveling salesman is in NP. There is no point debating this.

Edit: as others have pointed out: traveling salesman in in NP only when it is in its decision version. Otherwise the question does not make sense, as standard complexity classes are defined for decision problems, this is - for languages.

It's kind of imprecise, but the understanding in these situations is that you're talking about some bounded version of the problem. In TSP, it's common to mean the problem of "is there a solution of length less than N", and you're only verifying that the length is less than N, not that it's optimal.

We find that algorithms we have identified in P usually have small exponents. This may simply be selection bias, if we are poor at coming up with n^4+ algorithms.

/brainstorming

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/

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

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.