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

Can anyone suggest further reading on the topic? Anything from Computational Papers on P vs. NP to "Computation Complexity Classes for Dummies" is fine with me.

I studied this topic mainly from Algorithms text by Kleinberg/Tardos[1]. Like everything else, if you interested in proving problems NPC, read few examples from book and practice some on your own. Proving problems NPC of some common problems isn't very hard once you get hang of it.

http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321...

"Simplicity is the final achievement" -- Chopin, according to the video.

After a bunch of Googling the only source I can find for this is a 2007 religious apologetics book with no Amazon reviews. I can't even find a French version of the quote. Anyone know if it's legitimate? And a more interesting question: if no one has ever even reviewed this book, how is it all over the Internet as the source of this quote?

EDIT: Oops, looks like it is not religious apologetics. Still, I'm curious how a (presumably manufactured) quote like this spreads from such an obscure source.

i'm trying to envision a world where P and NP actually diverge, the universe is a fractal

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