NP problems

It sounds as if this is the end of the story but the subject has much more subtlety than this!

For example, there are the NP – Nondeterministic Polynomial – problems. These are such that if you guess a solution then you can verify that it is a solution in polynomial time but if you don’t guess a solution then you can’t find one in polynomial time.

Such NP problems are ones that look difficult but seem to have a loop hole that makes them easier!

For example if you want to write a program that solve jigsaw puzzles then you have to face up to the fact that you are not going to find a general solution that takes time proportional to a polynomial in N, the number of pieces. In fact you can see that it is roughly N! and this increases faster than any polynomial in N.
(N! is N factorial, for example 4!=4x3x2x1)

Finding a solution to a jigsaw is difficult but if someone gives you a possible solution you can check that it is a solution by examining each of the pieces. That is, checking a solution takes time proportional to N and thus solving a jigsaw is an NP problem.

Another, perhaps more important example in this day of public key cryptography, is testing a number to see if it is a prime. To do this you have to test to see if the number is divisible by numbers smaller than it. In this case the measure of the work to be done, N, is the number of digits in the given number and testing it for divisibility by all of the values from 2 to its square root takes time that is exponential in the number of digits. On the other hand it you give me a potential factor and ask me to test that it divides then I can do this almost without effort! 

In this case the question “is this number a nonprime” is NP because it only takes a single divisor to prove that it isn’t. You can think of the divisor provided as a “certificate” that the number in question isn’t a prime. On the other hand the related, or “dual” question, “is this number a prime” cannot be solved by providing a certificate. The reason is that a prime is something that doesn’t have a divisor and it is difficult to see how you could provide a single piece of evidence that would allow this to be checked.

To this day no one knows if this problem is NP or not because there is the possibility that a certificate for “primeness” could exist.

So to sum up, NP problems are hard to solve but easy to check. The thought at the back of everyone's mind is that perhaps if they are easy to check there should be an easy way to solve them. For example if you could create a way to guess a solution then you could check it polynomial time - with a really good guess perhaps you could always solve it polynomial time. We need to look at some of the subtlies of NP problems in a later chapter.

Being complete

So the great unsolved problem of algorithms remains to this day – can all NP problems be solved in polynomial time. Most people guess that the answer is no but so far there is still no proof of this and lots of theoreticians say that their hunch is that that answer is yes – the problems that look difficult really aren’t.

To make this task seem even easier there are some NP problems, NP Complete problems, which are representative of all NP problems in the sense that if you can solve one of them you can solve all of the NP problems.This is remarkable in itself it means that there are NP problems that are representative of all NP problem - solve one and you solve all of them.

Believe it or not, even with all of the effort spent on trying to find a polynomial solution to an NP Complete problem, no solutions have been found and most computer scientists are of the opinion that no such solutions exist. 

Non-computable problems

If you think that NP problems are a little bit odd consider the simple fact that there are problems for which it can be proved that an algorithm of any sort cannot be found. These are hard in a different sense. They are not out of our reach because of resource limitations. They are out of our reach because the logic of the universe prohibits us from inventing an algorithm that works out the answer we seek. 

The best-known example involves the halting problem for a Turing machine but the type of computer doesn’t really matter.

The halting problem is easy to explain – simply write a program that examines other programs to determine if they halt or loop forever. Obviously whether or not a program halts depends on the data it is fed so in this case we mean program to be code plus the data it operates on. 

In other words we want a program that can read the code of any other program plus its data and work out if the process halts or loops forever. This sounds as though it should be possible if not easy - but it cannot be done.

The simple reason why this cannot be done is that the program you have invented is a program and you can feed it itself and ask the question does it halt.

Yes this is an example of a self reference leading to a paradox and this is the sort of thing that you encounter all the time in this branch of computer science and logic.

From this stage it is easy enough to construct a paradox that if your program halts then it doesn’t and if it doesn’t then it does.

The details can be found in the books shown on the right among many others and in a later chapter, but you can get the general idea from the following three diagrams:

It starts off innocently enough – just create a program that tells you if another program stops or loops forever when reading itself as input

A slight modification is to add a loop that never ends if the program being tested ends. So now you only see a message if the program being tested ends otherwise the modified halting test loops forever.

Now we hit the paradox. Feed the modified program complete with a test subject into itself. Now if it stops it doesn’t, but if it doesn’t it does!

There are a lot of technical details needed to make this argument water tight but this is the general idea. If you know some other paradoxes you will recognize it as a variation on the Barber and similar paradoxes. The Barber paradox is if the Barber in the town has to shave everyone who does not shave themselves - who shaves the Barber?  If the Barber does then he doesn't etc.

There is a subtle point in all of these discussion that is usually glossed over and it can lead to serious problems. There is always an infinity hidden in this sort of proof. In the Turing machine case it is that the program can be as big as you like. This isn't the usual sort of infinity - its generally called finite but unbounded, see a later chapter. The point is that if we limit the size of the program to S say then we can write a program H that works out if it halts because you can't add H to S because that would produces a bigger program that might well be too big for you to deal with.

Exactly what makes something possible or impossible is very important in computer science. There are lots of cases where people use the halting problem to prove something of deep and practical significance only to have done so incorrectly because they haven't taken into account the unboundedness requirement. In fact there are lots of cases where misunderstanding what computer science is claiming stops practical advances. For example, there were arguments that satnav's were impossible because finding an optimum route was an NP problem. So just give up. Next time you use any route mapping program just remember that "good" isn't the same as "best". It is much easier to find a good route than it is to find the best route.

<ASIN:0465026567>