Those two examples are physically quite separated (maybe you like to drink your skinny latte with hazelnut and cream whilst sorting the records?). Consider this – for each extra item you want on your coffee, how much longer does it take than without that item? Would you think it a roughly constant increase in time for each added bit? Lets assume that to be the case. Say someone decides to have a black coffee – this will take a set amount of time, and for each item you add (chocolate sprinkles, warmed milk etc.), the time taken to make the drink will increase by a constant amount – this is a linear relation, which comes from the fact that if you were to plot the data from the coffee making on a graph, it would be a straight line and therefore linear.
Graph courtesy of Peter Acklam
This is not the case, however, for sorting the records should you choose the most basic method of taking a record, and comparing it to every other record. For each new record you add, the number of comparisons to sort these records will increase in an almost exponential manner (this name also is from the graph of the number of comparisons against the number of records – an example of this type of graph can be seen to the right) and if we assume that each comparison takes a constant amount of time, we can then deduce that adding extra records causes an exponential increase in time.
So, we have the coffee, which takes a linear amount of time for each extra ingredient, and we have sorting records, which takes an exponential amount of time for each extra record. How can this possibly apply to computing? Well, it just so happens that algorithms work in very similar ways. Some increase in linear amounts for each extra item you feed into them, and some follow an exponential time patterns. All algorithms can be put into groups of how they react to more inputs being given, such as linear-time, polynomial-time (which increase by a constant power for each extra input), exponential-time and even worse, such as x to the power of x, x being the number of inputs. The closer to linear-time or faster, the better, as the algorithm can be said to be more efficient. Computer scientists are constantly taking inefficient algorithms and trying to find ways of making them better.
So now we have our classes of algorithms, and we have a problem. We want sort some records, using our incredibly basic but functional method of comparing each record to every other record, and we need to do a lot of records, say 20 million. Now this is going to take a long time, no matter how fast our computer is (at this point I should inform you that the speed of the computer has no bearing on the classification of the algorithm, as all current computers can be reduced to ‘Turing Machines’, which I will talk about in future blog posts, and they all follow the same method of processing, that is taking a piece of data, dealing with it, then moving on, so they are fundamentally the same), so I want to use the most efficient method available. This is where P and NP come in.
P is the Polynomial class, in which all algorithms which are Polynomial-time or better are grouped, and Non-Polynomial-time which those which are exponential, or worse, are placed. P class problems are actually a sub-class of NP class, as illustrated in the image to the left – this may seem a little strange, but P problems are just NP problems made to be much more efficient. A given algorithm is worked on until it has reached its maximum efficiency, and at this point, it is classified into one of the groups. You will notice in this diagram ‘NP-Complete’. This is a NP subset which has two key properties. If we are given a solution to a problem which is in NP-Complete class, then it can be verified (i.e. checked to see that the solution is correct) in Polynomial time, and also, another, bizarre property arises. Any problem in the whole NP class can be converted into an NP-Complete problem by transforming the inputs in Polynomial time. This is a little hard to grasp, and describing it in detail is beyond the scope of this blog post, but in effect, you can emulate an NP problem using an NP-Complete problem by altering the inputs.
Here is the clincher. If any problem in the NP-Complete class is to be proven to be solvable in P, then all NP problems are solvable in P, hence P equals NP. The reason for this is by virtue of the fact of emulation – if the algorithm emulating the NP problem is P, then the NP problem must be solvable in P-time. Until then, P is not equal to NP
I can hear the cries of ‘So what?’, so in the next post, you will see exactly why this is such a big issue.