NP-Complete - A Rough Guide

This is a rough guide to the meaning of "NP-Complete". It is not intended to be an exact definition, but should help you to understand the concept.

These are just my personal ideas and are not meant to be "rigorous".

Its All About "Time to Solve"

If you measure how long a program takes to run when given more and more difficult problems, such as sorting a list of 10 items, 20 items, 30 items etc, you can then plot the times and come up with a function.

For example the time might increase by x², so a problem that is twice as hard takes 4 times as long.

That program would be in "P", as it is solvable in "Polynomial" time. In this case the polynomial is:

t = x²

But if the time went up exponentially or factorially, or something that exceeds what a polynomial can do, it would not be in "P". It is not solvable in "Polynomial" time.

Amazing Computer can do what normal Computers can't

Now, the "N" in "NP" refers to the fact that you are not bound by the normal way a computer works, which is step-by-step. The "N" actually stands for "Non-deterministic". This means that you are dealing with an amazing kind of computer that can run things simultaneously or could somehow guess the right way to do things, or something like that.

So this "N" computer can solve lots more problems in "P" time - for example it can just clone copies of itself when needed.

It is not a Super Computer (they are just very fast normal computers), it is really a "Non-deterministic" computer, but I am calling it an Amazing Computer to give you the idea!

So, programs that take dramatically longer as the problem gets harder (i.e. not in "P") could be solved quickly on this amazing "N" computer and so are in "NP". Thus "NP" means "we can solve it in polynomial time if we can break the normal rules of step-by-step computing".

Amazing Computers can also do what normal Computers can

Since this amazing "N" computer can also do anything a normal computer can, we know that "P" problems are also in "NP".

So, the easy problems are in "P" (and "NP"), but the really hard ones are *only* in "NP", and they are called "NP-complete".

It is like saying there are things that People can do ("P"), there are things that SuperPeople can do ("SP"), and there are things *only* SuperPeople can do ("SP-complete").

NP-Complete may not last

Oh, one more thing, it is believed that if anyone could *ever* solve an "NP-Complete" problem in "P" time, then *all* "NP-complete" problems could also be solved that way by using the same method, and the whole class of "NP-Complete" would cease to exist.

Travelling Salesman Problem

The classic example of "NP-Complete" problems is the Travelling Salesman Problem.

Imagine you need to visit 5 cities on your sales tour. You know all the distances. Which is the shortest round-trip to follow? ABCEDA? ADECBA?

An obvious solution is to check all possibilities.

But this only works for small problems. If you add a new city it needs to be tried out in every previous combination.

So this method takes "factorial time": t = n!

(Actually t = (n-1)! but it is still factorial.)

 

Lets say the program could solve a 20-city problem in 1 second, then a 21-city problem would take about 21 seconds to solve. And a 22-city problem would take about 462 seconds (over 7 minutes), and a 30-city problem would take 3 Million Years. Ouch!

Luckily, there are special ways to break the problem into sub-problems (called "dynamic programming", but the best still take "exponential time": t = 2n

So a program that solved 20 cities in 1 second would take about 10 minutes to solve a 30-city problem and a 60-city problem would take 35,000 Years.

But if we had the "Amazing Computer" mentioned above it could, for example, create copies of itself to check all the possibilities, and hopefully solve the problem very quickly.

 

Anyway, I hope this "quick and dirty" introduction has helped you ... now go and read something more rigorous.