Shortest Path

I would agree with you but there is something deeper going on because some problems are clearly not NP.

For example, the problem of finding the shortest path through a network clearly isn't NP.

Why not?

Because you cannot supply an extra piece of information that verifies that a path is the shortest. If I provide you with a path that I claim is shortest you still have to compare it to all the other possible paths to prove that it is. To be clear the problem is to find the shortest path - and the extra piece of information I supply is a path that I claim is the shortest. This isn't of much use in your quest for the shortest path because it is just one of the candidates for the honour.

Compare this to the seemingly similar problem of proving that a given path is not the shortest  - i.e. you don't actually have to find the shortest path just prove that the one given is or is not the shortest. This is NP because all I have to do is provide an example path, i.e. one path, that is shorter - I don't have to compare it to every possible path just one that is actually shorter. Thus given a path A it clearly isn't the shortest if you are given the extra piece of information that path B is the shorter. 

The key idea of an NP problem is that finding a solution is difficult and not in P but checking that a proposed solution is a solution is in P. 

Inverting The Problem

Many problems that are NP become non-NP if asked the other way around.

For example, a graph (another name for a network) is said to be `Hamiltonian' if there is a path through it visiting each node exactly once, see Figure 2.

Figure 2: This graph is Hamiltonian because there exists a path that visits each node exactly once -shown in red

Now for the questions:

1. Is proving that a graph is Hamiltonian in P?
   No, it takes exponential time to find a path that visits each node by examining paths until you find one.
   
   
2. Is proving that a graph is not Hamiltonian in P?
   Obviously not because you have to check every path to prove that a suitable one doesn't exist and so this must take longer on average than (1).
   
   
3. Is proving that a graph is Hamiltonian in NP?
   Yes - and guess what the extra information is? It's the path that visits each node exactly once. Once you have the description of such a path checking that it visits each node only once is trivial and obviously in P.
   
   
4. Is proving that a graph is not Hamiltonian in NP?
   No - because you can't give an extra piece of information that allows someone to check that a suitable path doesn't exist. You have no choice but to check them all and that's clear the same as (2).

At the end of this you should be able to see the difference between NP and non-NP algorithms.

Problems that we only know exponential solutions for are hard but they divide into two groups - some are really mean because you can't even provide a solution to the problem which can be checked in polynomial time, i.e. the non NP, and the group that aren't quite so bad because once you have a solution the fact that it is a solution can be tested in polynomial time i.e. the NP.

Making money the NP way..

You can make a list of other problems that involve searching, arrangements, matching etc. and they all exhibit the same find one example, or search the lot type of distinction.

The point seems to be that some algorithms that don't belong to P are really, really difficult while others, the NP set, contain an easy way out and aren't quite as difficult.

So what, I hear you say, this can't have any practical application! Well you are wrong - over 1000 important practical problems have been listed as being NP.

One of the most important revolutions in cryptography depends on just this distinction. In cryptography a function that is made easier to work out when you have some extra information is called a `trap door' function but this is nothing more than the NP property.

Using a trap door function you can implement `public key' coding. For example, if I choose two very large prime numbers p1 and p2 I can multiply them together to give m. Then I can quite happily make m public in the knowledge that the problem of finding p1 and p2 from m needs an algorithm that isn't in P, that is it takes a long time to factor m.

If I also use a coding method that makes use of m, the public key, but needs a knowledge of the factors of m to decode I have a cryptographic system that anyone can use to send me messages, but only I can read. This all only works if factoring is NP but not P and this hasn't been proved.

This is the basis of the RSA encryption algorithm and if you can find a fast way to factor large number, around 100 decimal digits, then you can crack RSA encryption and presumably make a lot of money.

There are a whole family of encryption methods based on NP algorithms, not just public key systems. For example, the controversial DES standard is based on an NP algorithm and again if someone can find a polynomial time algorithm for the same task they have access to a great deal of data that the owners assume to be secure!

NP complete

After a return to the real, well real-ish, world the final say has to go to the startling theory of NP algorithms.

I can't go into the details of how or why but it can be shown that there is an NP algorithm which is in a sense a `universal' representative of all the other NP algorithms.

This representative is called NP-complete, I suppose because in a sense it is the complete NP class. To be more precise an NP-complete algorithm can be shown to be convertible into any other NP algorithm and the conversion can be achieved in polynomial time. This sounds quite interesting, deep even, but harmless enough - but it has consequences.

If you can show that an NP-complete problem has a solution in polynomial time then so do all NP problems. If you can show that an NP-complete problem cannot possibly have a polynomial time solution then neither can any other NP problem. In a sense the entire set of difficult problems has been reduced to one.

Notice that not all problems in NP are NP-complete and there are some that you can find a polynomial solution to without affecting the status of the rest.

Indeed it turned out to be difficult to find the first NP-complete problem but it was demonstrated in 1971 that finding values that made expressions in propositional logic true was NP-complete. Once you have an example of an NP-complete problem you can identify others by showing that they can be reduced to the known example in polynomial time.

This is getting a bit deep and technical but what it means is that finding a polynomial time solution to an NP-complete problem such as the travelling salesman or the Hamiltonian also provides a polynomial time solution to such very different problems as factoring and testing primality. The opinion is that there is no polynomial time solution to an NP-complete problem but no one actually knows the answer and this doesn't stop lots of people publishing papers that prove the NP=P. 

There are parts of the overall theory that we haven't looked at - space complexity i.e. how much memory does an algorithm need, random polynomial time algorithms, circuit complexity and many others.

I hope that I have given you some insights into this fascinating theory, if you want to know more then the books listed in the right hand panel will take you further.

A Computable Universe - Roger Penrose On Nature As Computation    

NP-Complete - Why So Hard?       

Classic Nintendo Games Are NP Hard       

Physics Is NP Hard       

Pancake flipping is hard - NP hard       

<ASIN:0716710455>

<ASIN:0201000237>

<ASIN:0521424267>

<ASIN:0262033844>

<ASIN:0805071660>

<ASIN:1848001207>