To start, yes, I do like the question of P
versus NP and regard it as a very
important research question.

My reaction to the video lecture: Wow.
Amazing. Gee whiz. P versus NP. What a
biggie! Or is it?

There does seem to be a little, tiny,
itsy, bitsy point where the lecture went
off the track:

The lecture gave a big list of some of the
amazing things we could do if we could
prove that P = NP. Some of the items on
that list were protein folding (to cure
cancer) and scheduling.

Right? Not so much:

If someone has an important problem in
scheduling, protein folding or any of the
NP-complete problems, bring forward that
actual, specific, instance of the real
problem.

Why? Because there's no proof and little
evidence that finding a solution will be
too difficult for "current computers".

To this claim I can hear the complaint
now:

"But, but, but, the problems in
NP-complete are too difficult to solve for
current computers because as the problem
size increases, the best known algorithms
have running time that grows as an
exponential in the size of the problem,
and exponential growth limits us to
problem instances of just small down to
tiny size."

Yup, can hear that complaint.

Good news, guys: The complaint is false
and does not correctly explain the
challenge of NP-complete.

E.g,, 0-1 integer linear programming is in
NP-complete, but I can write down, as fast
as I can type, such problems about as big
as you please that I, or anyone, can solve
quickly just by simple inspection.

It's true.

E.g., for any positive integer n, consider
the 0-1 integer linear programming problem

max z = 1 * x1 + 2 * x2 + ... + n * xn

subject to

x1 + x2 + ... + xn = 1

x1, x2, ..., xn = 0 or 1

So, the error in the complaint is that
actually the question of P versus NP has
to do with worst case instances of the
problems. But practical instances are not
all worst case, and for many of the
practical instances we can get solutions.

So, for any particular actual, specific,
instance of a real problem, bring it
forward -- you might be able to get a
solution.

And, wait, there's more!

For a problem like scheduling, mostly what
is desired is just to save money in the
actual operations, say, airlines where we
need to schedule the planes for the
planned flights, the crews, and
maintenance for the planes.

Since the planes do fly, tough to convince
me that the scheduling is impossible.

So, if spending $200 million a month on
operations, an optimal schedule could save
$20 million, can find a schedule that is
approximately optimal and saves all but
the last $100,000, then take the
$19,900,000 savings and be happy.

The claim "we want to show that P = NP so
that we can solve all these important
problems" has been going on since the
cartoon early in

Michael R. Garey and David S. Johnson,
'Computers and Intractability: A Guide to
the Theory of NP-Completeness'.

where the mathematician stood before the
business executive and admitted that he
could not solve the executive's problem
but neither could any of the
mathematicians in a long line.

Likely nonsense: The mathematician was
likely just looking for a long term job
and actually not at all interested in
solving the executive's problem.

Why? Because there was no indication that
the executive's problem was large and
worst case and needed an exactly optimal
solution instead of a nearly optimal
solution. The executive's problem might
have been relatively easy to solve, with a
nearly optimal solution and maybe with an
exactly optimal solution.

Indeed, the book was from Bell Labs where
one of their interests was network design.
Well, since the phones did work, somehow
Bell did find feasible solutions.
Optimal? Maybe not.

So, what was "the executive's problem"
that was in NP-complete and "too difficult
to solve?". Maybe he just wanted to
design a telecommunications network to
have the needed performance and
reliability and, otherwise, get the cost
down as much as possible or nearly so.
Finding an algorithm that shows that P =
NP is very likely a significantly
different problem, not his problem, and
not necessary for his problem.

This erroneous belief that all large
instances of problems in NP-complete are
too difficult to solve is too common:
E.g., once I got a problem in allocation
of marketing resources. The instance was
0-1 integer linear programming with 40,000
constraints and 600,000 variables.

I thought for a day or so, typed in some
software, did some Lagrangian
relaxation, and in 905 seconds on a 90
MHz PC got a feasible solution guaranteed
to be within 0.025% of optimality. Close
enough for gumment work!

Then, later, as I was considering network
design for the Internet, I got an
interview at a network design startup in
Texas and mentioned the problem with the
600,000 variables.

Well, the whole technical staff was on the
other side of the table, had heard the
horror stories about NP-complete in
college, and concluded to a person that I
was claiming to have done the impossible
and had to be lying.

I left without a job offer, and they soon
went out of business.

By the way, Mother Nature does protein
folding, right? Hmm ....