Last night I finished my P vs. NP coverage, which took me far too long to finish off – exams and Computing coursework got in the way, but finally, I am free of them both! I had a nightmare of a day last Friday – 4 hours 45 minutes of exams on one day. The exams went okay overall – the Physics was as expected, but OCR seemed to have finally gotten the timing right after three attempts, Mechanics 2 wasn’t too bad but had some particularly nasty questions in it, and Statistics 2 had a few dodgy questions as well. Even so, I think they went all right, but the revision for them was tricky. On top of the pain of actually doing the revision, I had to balance between three separate subjects, all for the same day. I decided to place most emphasis on Physics revision, because that is the one which ‘counts the most’ so to speak – Mechanics and Statistics are part of Maths overall, and I already have an A* in Single Maths as far as I know – I needed around 53/100 each on Further Pure 3 and Mechanics 2 to get an A in Further Maths. My aim is A*, but I won’t be hugely disappointed if I don’t get that. Physics, on the other hand, is far from settled, as the final module of both years carries more weight than the January Module, and so can decide the grade itself. In addition to that, there was a lot more to learn for Physics than for Mechanics and Statistics put together. This module seemed to want you to know huge amounts, but maybe that was because the topics were quite separate, for example Medical, Nuclear, Cosmology were all in this module. Furthermore, I had done a lot of Mechanics and Statistics revision during college, as we always finished the Maths syllabi very early, leaving loads of revision time.

Next stop is university, reading Computer Science. That should be great, I can’t wait for it. Before that though, is summer, which promises to be special. I’ll be going to the British Grand Prix and V Festival, and both are going to be amazing.

In terms of the blog, I want to update it more frequently. I’ll probably do a general post every few days, and a more technical, maths, computing or F1 article every so often.

Until next time, have a good one!

P.S. If you want to learn more about P vs. NP, there are loads of great resources on the internet. I only glossed over it, and there are other factors like memory space as well as time. A good but expensive book is Algorithmics: The Spirit of Computing by David Harel and Yishai Feldman, if you wish to learn more, specifically from the algorithmic viewpoint. A highly recommended book on general Computer Science is The (New) Turing Omnibus, which I own and am currently reading.

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.