> What is your point? That if we were all totally satisfied with half-ass solutions and non-answers, we wouldn't have to worry P = NP?
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.