What can be computed?

We tend to think that computers can do anything. If you can ask a question then a computer can help you answer it. Perhaps at the moment it might just be beyond their reach but if you wait long enough the hardware will improve enough to get you an answer. However the truth isn’t quite as simple and the question “what can be computed?” doesn’t have a straightforward answer.

In some ways the answer to the question is almost more illuminating about the nature of the universe than a simple answer would be. There is also the small matter that “what can be computed” depends on your definition of what represents a practical procedure. Some might be only interested in computations that can be completed in a reasonable time at reasonable cost. Others might be interested in what happens if you are prepared to allow any amount of hardware and time to be thrown at a problem.

What might surprise you is that even if you do allow any amount of computational power to be dedicated to a project there are still things you cannot compute!

First let’s look at the more practical aspects of computation.

Practical algorithms

When a programmer or theoretician thinks up a method of working something out, i.e. an algorithm, there’s a variety of concerns. The first is that the algorithm should give an answer in a reasonable time.

This sounds like a simple requirement but an algorithm that works in a reasonable time for a small-scale problem can turn out to be unreasonable when the problem becomes bigger.

Computer scientists classify algorithms according to how they scale as the problem gets bigger. If N measures the size of the problem, the number of data points, dimensions, records and so on, ideally we would like an algorithm that takes the same time as N gets bigger. Usually however the time taken to complete a task depends on N or N squared or some power of N. Such algorithms are said to take “polynomial time” and these are regarded as good algorithms. A polynomial time algorithm might well turn out to take too long in practice but you can always double the speed of the machine or invent something that makes it more reasonable.

The difficult algorithms are the ones that work in non-polynomial time. These include problems that don’t have a known solution at the moment and those that take exponential time, i.e. that take longer than any polynomial for large enough N. Non-polynomial time algorithms are the ones that blow up to the point where what you thought was slow for 10 items suddenly takes more time than the universe has to run for 11 items. Problems for which there is only an exponential time algorithm are called “difficult”. How do you know that a problem is difficult? There might be a better algorithm that has yet to be discovered.

Some problems are provably difficult because you can show that there can be no polynomial time algorithm that solves the problem. At the extreme there are the provably unsolvable problems for which it can be shown that no algorithmic solution can be found.

The time it takes to process N items is an important factor in how practical an algorithm is

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

Being complete

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

<ASIN:0198604424>

<ASIN:0534949681>

<ASIN:1848001207>

<ASIN:0465026567>