NP-complete isn't always hard
It&#x27;s easier than in the OP (original
post):<p>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 <i>NP-complete</i> problem.  Here
NP abbreviated &quot;non-deterministic
polynomial&quot; that can use a little
explanation (below).<p>Writing a computer program to solve Joe&#x27;s
problem is easy.<p>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&#x27;s problem is harder
than Joe&#x27;s in the sense that the same
computer program will run longer for Sam.<p>Actually, a computer program that will
also do <i>well</i> (explained below) for Sam
is also easy to write, should be the same
program that did well for Joe.<p>Now we can get into the &quot;hard&quot; 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 <i>worst case</i>, no matter
where the cities are.  Hmm.  They want a
<i>perfect</i> program.<p>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 <i>polynomial</i> running time.<p>NP?  One approach is to be
<i>non-deterministic</i>, 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.<p>Biggie point:  So far no one knows if a
program that runs in time n^k is possible.<p>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.<p>Uh, in practice, if are willing to get
close on nearly all real problems, we are
in quite good shape in practice.<p>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 <i>space</i> with Euclidean
distances.  Then for the solution, just
follow the spanning tree omitting any
trips don&#x27;t have to take.  A paper with
this solution is old.<p>It goes on this way:  There are lots of
problems in <i>combinatorial optimization</i>,
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 &quot;complete&quot; means.<p>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 <i>well</i> on nearly all
such practical problems.  A source of such
0-1 ILP problems is ILP <i>set covering</i>.
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 <i>tour</i>.  There are
lots of candidate tours, but a lot of them
can&#x27;t fly because of scheduled arrival
times, limits on loads and distances, etc.
So, call the candidate tours that can fly
<i>feasible</i>.  For each of the feasible
tours, find the operating cost.  Then the
problem is to <i>cover</i> the <i>set</i> 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 <i>set covering</i>.<p>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 <i>enumeration</i>
work.  It&#x27;s fairly general stuff.  Keep it
in mind; you might find another
application.<p>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&#x2F;applied math
Ph.D.<p>With such a set covering problem, by doing
<i>well</i>, we mean saving a lot of money
and&#x2F;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 <i>duality</i>,
Lagrangian relaxation, etc., can tell when
can&#x27;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&#x27;t save any more
than 0.025% more of the total cost.  That
problem had 40,000 ILP <i>constraints</i> and
600,000 ILP 0-1 variables -- that is,
might not be regarded as <i>medium</i> sized
and not small and trivial.<p>So, generally can do <i>well</i> for Joe and
even Sam even if the question about
NP-complete, polynomial times, minimum
cost, and worst case problems is not
solved.<p>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 &quot;in practice&quot;?  They care a lot
about the $5 million and don&#x27;t want to
decline to save the $5 million because
there might be $100 more to be saved that
they don&#x27;t know how to save.<p>By now the techniques of 0-1 ILP and more
generally discrete or combinatorial
optimization, e.g., in the field
<i>operations research</i> or <i>optimization</i>,
are old, 50+ years old.  There are lots of
carefully written, clever books and papers
and lots of mature software.<p>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&#x27;ve been able
to do <i>well</i> for many decades, in
practice.<p>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 <i>discrete</i> optimization.  At
the start of their book they confessed
that they really didn&#x27;t know how to
<i>solve</i> the design problems and then gave
a cartoon showing a long list of other
people who didn&#x27;t know either.  But by
<i>solve</i> 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.<p>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&#x27;s biggest
examples, for some work important in
practice, of letting the perfect stand in
the way of the very good.