It's easier than in the OP (original post): Joe is a traveling salesman and has to visit 10 cities, each once. He wants to minimize the driving distance. Tha

It's easier than in the OP (original post): Joe is a traveling salesman and has to visit 10 cities, each once. He wants to minimize the driving distance. That is an example of an NP-complete problem. Here NP abbreviated "non-deterministic polynomial" that can use a little explanation (below). Writing a computer program to solve Joe's problem is easy. Here in one step more generality: Let the number of cities be the positive integer n. For Joe we had n = 10. Joe has a friend Sam with the same problem, but for Sam n = 1000. Sam's problem is harder than Joe's in the sense that the same computer program will run longer for Sam. Actually, a computer program that will also do well (explained below) for Sam is also easy to write, should be the same program that did well for Joe. Now we can get into the "hard" stuff: Joe and Sam are picky and want the minimum distance, down to the last tiny fraction of 1 inch, perfectly so, all the time, including the worst case, no matter where the cities are. Hmm. They want a perfect program. Here it appears that the running time of the perfect program on the worst case grows like 2^n, exponential growth. Joe and his n = 10 and especially Sam with his n = 1000 would be very happy with growth of the worst case running time like n^k for some positive integer k. That is, the want n^k polynomial running time. NP? One approach is to be non-deterministic, that is, use a random number generator to pick the cities and maybe get very lucky, and that is so easy to do can do it in polynomial time. Biggie point: So far no one knows if a program that runs in time n^k is possible. But, remember, Joe and especially Sam are picky -- they want perfection, the minimum distance down to the last tiny fraction of 1 inch all the time on worst case problems. Uh, in practice, if are willing to get close on nearly all real problems, we are in quite good shape in practice. How? For Joe and Sam, one way is to build a minimum spanning tree of the n cities -- there are at least two simple, fast algorithms for that. Then exploit that the cities are in a space with Euclidean distances. Then for the solution, just follow the spanning tree omitting any trips don't have to take. A paper with this solution is old. It goes on this way: There are lots of problems in combinatorial optimization, all NP-complete, and if have that there is a polynomial algorithm for any one of them then there is for all of them, which is what the "complete" means. But, e.g., for one of the relatively general (in practical terms of simple problem formulation) NP-complete problems is 0-1 integer linear programming (ILP), can tweak the simplex algorithm of linear programming to do well on nearly all such practical problems. A source of such 0-1 ILP problems is ILP set covering. E.g., I encountered one of those: Consider FedEx and its airplanes, the cities to be served, and the loads to be carried. Each plane leaves Memphis, makes its stops, and returns to Memphis. Call what one plane does a tour. There are lots of candidate tours, but a lot of them can't fly because of scheduled arrival times, limits on loads and distances, etc. So, call the candidate tours that can fly feasible. For each of the feasible tours, find the operating cost. Then the problem is to cover the set of all cities to be served with the feasible tours such that the total cost is minimized. That is an example of 0-1 ILP -- ILP set covering. 0-1 ILP set covering is nice, simple stuff: Get to evaluate the individual tours, or what stands in for those in some other problem, considering lots of really goofy costs and constraints, maybe even some probabilistic stuff where get to take averages, and then do the optimization itself after this initial enumeration work. It's fairly general stuff. Keep it in mind; you might find another application. The FedEx airplanes are expensive. A good set covering solution should have saved FedEx a lot of money, a significant fraction of their total operating cost otherwise. The FedEx founder liked my lecture on set covering, assigned me to do the work. But the promised stock was late, so I want for a pure/applied math Ph.D. With such a set covering problem, by doing well, we mean saving a lot of money and/or nearly all the money to be saved even if had a solution that minimized cost down to the last fraction of an inch or dollar or whatever were trying to save. And, nicely enough, often the 0-1 ILP techniques, e.g., some cases of duality, Lagrangian relaxation, etc., can tell when can't save any more than, say, another 1% of the total. One problem I did once, in 0-1 ILP, but not for FedEx, with my solution knew that couldn't save any more than 0.025% more of the total cost. That problem had 40,000 ILP constraints and 600,000 ILP 0-1 variables -- that is, might not be regarded as medium sized and not small and trivial. So, generally can do well for Joe and even Sam even if the question about NP-complete, polynomial times, minimum cost, and worst case problems is not solved. Net, in practice, that a problem is in NP-complete, in practice, is nearly always of no concern, in practice. In practice, if save $5 million a day and a perfect solution might save another $100 a day, in practice no one cares, in practice. Did I mention "in practice"? They care a lot about the $5 million and don't want to decline to save the $5 million because there might be $100 more to be saved that they don't know how to save. By now the techniques of 0-1 ILP and more generally discrete or combinatorial optimization, e.g., in the field operations research or optimization, are old, 50+ years old. There are lots of carefully written, clever books and papers and lots of mature software. The question of a polynomial algorithm for the NP-complete problems is interesting, curious, one heck of a challenging research problem, maybe a start on some really important work in math and applications of wide variety, maybe a pillar of what is fundamental about computing, etc. But, in practice, for Joe, Sam, Fedex, and more, we've been able to do well for many decades, in practice. Early in the discovery of NP-complete problems there was a book written at Bell Labs. Bell needed to do network design, and that was discrete optimization. At the start of their book they confessed that they really didn't know how to solve the design problems and then gave a cartoon showing a long list of other people who didn't know either. But by solve they were picky like Joe and Sam -- minimum cost down to the last tiny fraction of the last dollar or penny even on worst case problems. Since then at least experience shows that their confession and cartoon were way too pessimistic, that for saving the first, say, 99% on essentially all the actual, practical problems was doable. Their attitude was one of the planet's biggest examples, for some work important in practice, of letting the perfect stand in the way of the very good.