The set NP

The idea of polynomial time algorithms is relatively easy to understand but once you start classifying algorithms you can't help but discover other interesting classification.

For example, there is the class of NP or Non-deterministic Polynomial algorithms.

An NP algorithm is something that can be worked out in polynomial time if an additional piece of information is provided.

For example, if you are trying to find the factors of a number that has been constructed by multiplying two primes together i.e. find the factors of z where z=p*q with p and q prime, then it will take exponential time. However, if someone tells one of the factors i.e. either p or q then you can find the other factor by simple division and so finding the factors is in P if you are given one of the factors.

Having a factor changes the task from exponential to polynomial and this makes it NP.

The reason for the name Nondeterministic Polynomial is a bit strange. Imagine testing for the factors of z by just picking a random number to see if it divide into the number exactly. You might hit lucky and so obtain the factors and as the division algorithm is polynomial you might call this a non-deterministic polynomial time algorithm.That is the fact that the problem can be solved in polynomial time when an extra piece of information is supplied allows the problem to be solved by guessing.

Notice also that all of the algorithms that are in P are also in NP because they are still polynomial if you supply any random unconnected piece of information.

You might think that NP is a silly idea because being given the extra piece of information to make a problem solvable in polynomial time is a cheat in that in most cases getting the extra information involves solving the problem anyway.

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.

Compare this to the seemingly similar problem of proving that a given path is the shortest or not. This is NP because all I have to do is provide an example path that is shorter - I don't have to compare it to every possible path just one that is actually shorter.

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

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.

<ASIN:0716710455>

<ASIN:0201000237>

<ASIN:0521424267>

<ASIN:0262033844>

<ASIN:0805071660>

<ASIN:1848001207>