Polynomial time

Most algorithms run in something like O(n^x) where x is some number like, 1,2,3... Such methods are said to run in polynomial time. Such a classification would be pointless unless there were algorithms that didn't run in polynomial time and of course there are.

This in itself is a bit strange. Surely a big enough value of x will do the trick? The answer is no. For example, there are algorithms that run in exponential time, i.e. O(e^n), and it isn't difficult to show (which is maths speak for "it takes quite a bit of theory to show") that no matter what value of x you choose there is a value of n such that O(e^n) is bigger than O(n^x).

What this means is that a polynomial algorithm may take a long time to run but it is nowhere near as bad as an exponential time algorithm.

The set of all algorithms that run in polynomial time is called, not unreasonably, P and the question of whether an algorithm is in P or not is an important and sometimes difficult to answer question.

The algorithms that increase more steeply than polynomial time are generally referred to as exponential time algorithms although this is a misuse of the jargon because many run in a time that has nothing to do with exponentiation.

For example, the travelling salesman's problem, i.e. find the shortest route between n cities, has an obvious solution which runs in O(n!).

(Note: n!=n*(n-1)*(n-2)..*1 e.g. 5!=5*4*3*2*1)

This is a factorial time algorithm but it is still often referred to as requiring exponential time.

Whatever you call them algorithms that are in P are usually regarded as being reasonable and those not in P are considered unreasonable.

Nothing but the best

Now at this point we reach a stage where the reasoning undergoes a subtle change that is often ignored in textbooks. Up until now we have been talking about algorithms belonging to P but really we would like to answer a slightly more general question. Is it possible to find an algorithm that achieves some result in polynomial time or is such a thing impossible?

This shifts the emphasis from finding the order of any given algorithm to finding the order of the best algorithm for the job - much more difficult.

For example, it is isn't difficult to show that multiplying two numbers together using the usual `shift and add' algorithm is O(n^2) where n is the number of bits used to represent the numbers. This means that multiplication is certainly in P but is O(n^2) the best that we can do? Is there an O(n) algorithm?

Certainly you can't produce an algorithm that is faster than O(n) because you at least have to look at each bit, but can you actually reach O(n)?

Well before you spend a lot of time on the problem I'd better tell you that it is difficult and the best that anyone has come up with is the odd-looking O(nlog n loglog n), which is a lot better than O(n^2) but still not as good as O(n).

The example of multiplication is easy to understand and it is easy to prove that it is in P by describing an obvious O(n^2) algorithm.

Now consider an equally innocent looking problem - proving that a number is prime (that is has no factors). For smallish numbers this is a trivial job. For example, 12 isn't a prime because it can be divided by 2 and 6 to name just two examples, but 13 is prime because it has no factors.

The simplest method of proving that any number, z say, is prime is to try to divide it by 2, 3 and then all the odd numbers up to SQRT(z). If you analyse this method you will discover that it is O(2^n) where n is the number of bits used to represent the number and this is exponential and so not in P. But this doesn't prove that testing for primes isn't P because there might be a better way of doing the job.

Recently the problem was solved and now we know that testing a number for primality is in P but that it took so much effort should indicate that it is in general difficult to prove that something can be done in P or not.

You should be able to see that the problem is that if you can find an algorithm for a task that runs in polynomial time then you have proved that the problem is in P but if you can't it might be that you just haven't looked hard enough. There are some problems where you can actually prove that there cannot be a polynomial time algorithm but there are also a lot of cases where we just don't know.

<ASIN:0262033844>

<ASIN:0470229055>