Polynomial time v Exponential 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 - as already mentioned they are computationally equivalent in some general sense to a set of nested loops. 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 always do the trick?

The answer is no.

For example, there are algorithms that run in exponential time, i.e. O(eⁿ), and it isn't difficult to show (which is usually 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ⁿ) is bigger than O(n^x).

A couple of things to notice is that the difference between eⁿ and n^x is that in the first a fixed value is raised to an ever increasing power i.e. e¹, e², e³, and so on but in the second an ever increasing value is raised to a fixed power e.g.  1⁴, 2⁴, 3⁴, and so on... Seen in this light it isn't surprising that eⁿ always over takes n^x for a fixed 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.

The jargon is slightly murky but we say that anything that exponential time or worse is exponential. More accurately exponential time is generally defined to be O(a^poly(n)) where a is a constant and poly(n) is any polynomial in n.

You will also hear O(n) referred to as linear time, O(n log n) as quasilinear time because it doesn't increase much faster than linear and O(a^{poly(log n)}) as quasi-polynomial time because it doesn't increase much faster than polynomial time. There are others.

Finally notice that the constants in these definitions largely don't matter and it is usually to take a to be 2 for no particular reason.

It also doesn't matter what the base of the log is taken to. Although base 2 is common all log functions increase equally fast for big enough n.

Nothing but the best

Now at this point we reach a stage where the reasoning undergoes a subtle change that is often not emphasised enough 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.

You can also ask what the best algorithm is if you specify your computing resources - a Turing machine for example or a finite state machine and so on. There are algorithms that run in P for some classes of machine but not for others. This is where things can get complicated and subtle for the moment we will ignore the type of computer used for the algorithm apart from saying that it is a standard machine with random access memory - a RAM machine. 

It is interesting to note however algorithms that run in sub-polynomial time can change their complexity when run on different types of machine.

How Fast Can You Multiply?

So the really interesting questions are not about how fast any particular algorithm is but what is the fastest algorithm for any particular task.

For example, it is isn't difficult to show that multiplying two numbers together using the usual `shift and add' algorithm is O(n²) where n is the number of bits used to represent the numbers.

This means that multiplication is certainly in P but is O(n²) 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(n log n log log n), which is a lot better than O(n²) but still not as good as O(n).

Is there a faster algorithm? Who knows. You would need a proof that said that it was impossible to perform multiplication faster than the stated algorithm.

You can see that in a very deep sense the order of the best algorithm tells you a lot about the nature of the task being performed. Is it just an easy task that happens to look difficult in this form - or is it irreducibly difficult?

Prime Testing

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²) algorithm. So we might want to argue about how fast it can be done but there is no question that it is in P.

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ⁿ) where n is the number of bits used to represent the number and this is exponential and so not in P i.e. prime testing using this algorithm at least isn't P. 

But this doesn't prove that testing for primes is or isn't in P because there might be a better way of doing the job. But given the apparent complexity of factoring a number it seems very reasonable that a polynomial time algorithm for testing primality isn't a likely proposition but...

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.

It is also worth thinking for a moment about the related task of factoring a number. To prove that a number is non-prime you simply have to find a factor but proving a number prime or non-prime can be done in polynomial time. What does this have to say about the task of factoring a general number? If you can factor a general number in polynomial time then you can crack a lot of code that are based on the fact that you can't.

The route that we took to find an algorithm for testing a number for primality is also interesting. At first we invented probabilistic tests for primality. You computed something and and if the algorithm ends in a value that isn't 1 then the number is not a prime. If it does end in 1 you haven't proved that the number is prime but the probability is that it is. To be more exact if the number isn't prime the test has a 75% probability of not ending in a 1. So after one test that ended in a 1 you can conclude that there is a 25% chance of the number isn't a prime. After another test the doesn't end in a 1 the chance that the number isn't prime is 6.25%  or putting it the other way the probability that it is prime is 93.75%. If you keep testing you can make the probability as close to one as you want.

The existence of a probability based algorithm that was in P was an indication that there might just be a deterministic algorithm in P. This turned out to be true. Interestingly the probability based test is still in use because in practice it is so much quicker than the deterministic test.

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 i.e. factoring is not in P.

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 might seem a bit strange at first. 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, i.e. random, 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.

<ASIN:0262033844>

<ASIN:0470229055>