tangoblog

A blog, under construction

To Continue…

Jun 25

Posted by Matt in Uncategorized

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.

2 Comments

P vs. NP – Why should you care? Part 3

Jun 25

Posted by Matt in Computer Science

Ok, so we have now established what P and NP are, and how they are interdependent. What hasn’t yet been covered though, is why you should care. It might seem tricky to answer – why should a non-geek care? In fact it isn’t hard to answer at all. The safety of your money depends on P vs. NP.  The cost of computer-driven devices may also depend on P vs. NP. It’s even arguable that some people’s jobs even depend on P not equalling NP.

In terms of money safety, I am speaking of the encryption method called Public Key Cryptography. This is the method that online shops use so that you can transfer payment details without people being able to eavesdrop on you, and gain access to your money. Within a lot, if not all of the Public Key Encryption algorithms, a huge number is generated and used as part of a private key, which only you and your computer knows. They crux of this is that the private key often consists of large prime factors, and as it stands there is no prime factorisation method for current, non-quantum computers which is in P-time, so if you have a large enough number,  it is practically impossible to find the factors and hence your private key. If P was to equal NP, then prime factorisation would be in P-time, hence rendering Public Key Encryption weak, and making your payment transactions insecure.

A fascinating result of P equalling NP would be that the Travelling Salesperson Problem would be in P-time. This problem deals with route-finding, and at present, it has no P-time solution, making it practically unusable for routes which include a lot of stopping points. The obvious applications of this would be logistics, as being able to quickly plan a tour of 500 stops based on fuel used and distance, among other factors, could save a lot of money compared to current methods, as well as reducing environmental impact through cutting back on wasted mileage. Surprisingly though, this problem, if solved in P-time would make the production of microchips a lot more efficient. This would be due to the routing of the wires between components – there are many components in single microchips, and wiring them up is likely to involve a lot of wastage, which is passed on to the customer through extra cost. By applying Travelling Salesperson to the designs of the chip, the wiring could be much more efficient, saving in production costs and hence saving the consumer money. As microchips are used in a huge amount of products now, from computers to air-fresheners, this will allow the consumer to save a lot of money on various products.

This brings me to my final point, which is a more worrying one. Should P equal NP, then a lot of jobs done by humans as computers could not do them efficiently might disappear. Business is ruthless, and the unfortunate reality is that if a computer can do it, the human is no longer needed. Jobs which might be affected by these developments would be route-planning, some clerical work, among many different fields where this would hit. For this reason, a lot of people working in these fields will probably be praying for P not to equal NP, if they know about it at all.

That brings me to the end of this computing journey, and although a lot of words have been written, I have only covered one small part of Computer Science as a whole. Hopefully you will have seen from this that P vs. NP has real world consequences, and solving it is a very big deal – there is a $1 million reward for the person who submits a correct solution to it, from the Clay Mathematics Institute as part of the Millennium Prize Problem list. Personally, I don’t believe P equals NP. I think that by now, a problem in NP-Complete would have been found that is actually a P-time algorithm, and we would have been done with it. As it stands, there are over 3000 NP-Complete problems, and none have yet been found to be in P-time. As for the actual result? Well, we’ll have to wait and see. Let’s just hope we don’t end up with another Fermat’s Last Theorem.

4 Comments

P vs. NP -Why should you care? Part 2

Jun 24

Posted by Matt in Uncategorized

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.

An exponential graph

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.

No Comments

P vs. NP – Why should you care?

Apr 9

Posted by Matt in Computer Science

If you don’t know much about Computer Science – and lets face it, a lot of people don’t, it isn’t the most popular topic, like it or not – then you probably haven’t heard of a problem called P versus NP. Look at the Wikipedia Page, and terms like ‘complexity classes’, ’subset-sum problem’ and ‘polynomial time’ are all mentioned in the first few paragraphs. It may seem totally abstract, and unrelated to the ‘real world’, and as an isolated, theoretical problem it can be. However, when you look at what this problem applies to, then it becomes a little clearer that this issue is much larger than it looks. I want to explain the problem as clearly as possible, so that the average computer user can appreciate it. To avoid a wall of text, I’ll be tackling it over a few posts, it is a big topic after all!

First, lets look at what it applies to – algorithms. Algorithms are the things which allow computers to perform as they do. The definition mentions ‘an effective method for solving a problem’, and it pretty much comes down to that. They are lists instructions which perform tasks, and almost always take some sort of input (for example the name of an item to search for), they do some processing, then sometimes they give output (i.e. a message to say if the item was found, continuing the previous example).

Lets have a look at how an algorithm may fit into everyday life.Image from http://en.wikipedia.org/wiki/File:LampFlowchart.svg , produced by Wapcaplet

The picture to the right is a flowchart representation of figuring out why a lamp doesn’t work. If you follow the chart, there are decisions to be made, and processes/outputs based on those decisions. Each item on the flowchart represents an instruction, input (the lamp not working) is given, and a series of outputs are provided for different outcomes. From this, we can deduce that this is an algorithm – it has well defined steps to achieve a task.

Many things we do every day can be expressed as algorithms, however as the tasks get more complicated, so do the algorithms. Making a cup of tea/coffee, or pouring a drink, is relatively simple and requires few steps – even when someone decides they want a skinny latte with hazelnut and cream, warmed to 51 degrees Celcius (if that even exists). In contrast, sorting a randomly ordered filing cabinet into alphabetical order is somewhat harder even with about 100 records. Now how about sorting 5 million records? This would take much, much longer, unless you found a particularly efficient method.

Now at this point, with me talking about coffee and filing, you may thing I have gone way off the track to explaining the P vs. NP problem. This trip however, is a necessary detour; bear the previous examples in mind – in the next post, I’ll explain what these seemingly random algorithms have to do with our main issue.

No Comments

The Titchmarsh Outrage

Mar 30

Posted by Matt in General stuff

You might be aware that recently, on The Alan Titchmarsh Show, there was a ‘debate’ about video games. As usual, it was discussing if games are too violent, what effect they have on kids, etc. If you haven’t seen it already, watch it here – ideally before reading the rest of this post (otherwise it won’t make much sense).

The first time I watched it, it filled me with rage. The second time I watched it, the same happened, so this time I decided to send an email to ITV about it. Below is that email.

Dear Sir/Madam,

After seeing the ‘debate’ about video games on the Alan Titchmarsh show, 19th March 2010, I feel the need to complain to you. When having a discussion such as this, usually, those related to the area in question are asked to speak on it. Obviously, this was not the case as the program fielded Julie Peasgood, who as far as I am aware has little to do with video games, either for or against. I understand that it is not always practical to have a full panel of experts, but the guests should at least have some idea of what they speak about. She clearly did not – her points were uninformed, and regularly wrong. Some examples of this include her mentioning of some research conducted in America, but then she failed to indicate who had conducted this research; she then claimed this was a proven link, i.e. a fact. In addition, she failed to provide any examples of the games that she wildly brandished to ‘promote hatred, racism, sexism, and they reward violence’. Instead she stated that ‘video games are addictive, they promote hatred, sexism, and they reward violence’, which as far as I can see infers all games under this banner – I can safely say that she is fundamentally and completely wrong. The games that she describes form a small section of all games released, see, for example, the game ‘Singstar’, as mentioned in the debate – this fits under none of those headers.

At this point, I have to also add my displeasure at the host into this – there was an element of bias presented by him, and I believe that as a host of a debate, you must endeavour to remain impartial. I do not, however, think that this bias was intentional, but instead a product of a lack of research. He was not aware that games are rated using exactly the same system as films are, and that these ratings are reinforced in retail outlets. This is basic knowledge, and this should have been considered before the show was filmed. This meant that he repeatedly put points forward on issues which were irrelevant, such as the point about stopping children acquiring games for adults. Following on from the point made previously about the unnamed research, the host referred to this as fact – a single piece of research, even when it exists and is cited properly, rarely indicates ‘proven facts’ especially in the fields of social science where facts are made up of many pieces of research considered together. The host did not seem to pick up on this, and made an ill-advised vocabulary choice due to this. When Tim Ingham, the editor of CVG, responded with fully cited and relevant research, he was booed by the audience.

Following on, I understand that everyone is entitled to their views, and I absolutely and whole-heartedly support this notion, but to boo and shout at someone whilst they are talking is disgusting and outrageous behaviour – this type of thing should have been stopped by the studio crew. Of course, you don’t want a silent, non-reactive audience, but common decency should dictate not to be abusive towards people when in a debate – just because people have opposing views does not mean that it is okay to interrupt them. There is a line that was crossed; the booing was on this line, but the interruption, mocking laughter and similar was beyond.

To conclude, I would like to say again that I agree with free speech and the idea of everyone being allowed their own opinions. I do not, however, think that it is acceptable to skew debates as this programme did by constantly forcing Ingham onto the defensive and taking questionable points as fact. I strongly recommend that in future, when debates on this programme are undertaken, an effort to avoid bias toward a certain viewpoint is made, and also, guests selected have some idea about what they are debating. In this debate, opinions were voiced as fact, which undermines the quality of the discussion. As a final point, it would be worth the host doing research on unfamiliar topics in future, as this also is detriment to the debate – in this instance, his ignorance to the situation forced him to bias.

Regards,

Matt Smith

I sent this earlier today. A few minutes before starting this blog post, I received this reply:

Dear Matt

Thank you for your recent email regarding The Alan Titchmarsh Show which has been forwarded to Channel Television.

Channel Television is the Channel 3 broadcast licensee appointed by ITV Network to be responsible for the compliance of this particular programme.  Should you wish to contact them, you may do so by email at the following address:-

feedback@channeltvlondon.co.uk or by telephone on 0207 633 9902 during normal office hours.

Regards

ITV Viewer Services – TT

Lets see if they respond, and what they have to say if they do. I really hope they decide to, it would be interesting to see what they have to say.

Tags: ,

1 Comment

Restart

Aug 24

Posted by Matt in Guitar, Muse, Music

The Resistance Album cover, property of copyright holder (Warner Bros/graphic artist/otherwise)

'The Resistance' Album cover, property of copyright holder (Warner Bros/graphic artist/otherwise)

So, no post in a long time, so here is a quick one. New Muse album out soon, ‘The Resistance’. It looks fantastic, can’t wait – it’s inspired me to start learning Muse songs on the guitar – Plug In Baby and City of Delusion to name a few. Now looking at guitar multi-effects pedals, will post again soon.

Tags: , , ,

2 Comments

British GP

Jun 24

Posted by Matt in Cars & Driving, F1

What a weekend! I spent it at Silverstone, for the British Grand Prix, and it was phenomenal. Going with a friend, we stayed were on a sort of package trip, with a coach there, stopping in a hotel, and general admission tickets for Saturday and Sunday all included. Ideally, we would have been camping, but due to how late we sorted it out, it wasn’t really possible.

Stopping in a hotel has its good sides: no long queues for showers or toilets; a good bed to sleep in; often comfy surroundings; often a decent breakfast. For the hotel we were in, these were mostly true, but then there were the negatives – the main one being how far away we stayed from Silverstone Circuit. It was about 57 miles, which turned out to be about an hours drive, and luckily the driver managed to find a route in with minimum traffic.

For those who have been to a GP before, or any major motorsport event really (but especially F1) you will know how tremendously busy it is. It really is quite unbelievable. On the Saturday, which was F1 Practice 3 and Qualifying, it was very busy, but Sunday was something else. This is where the hotel comes into it. We only set off each day at 8:30 am, which may seem early, but for a Grand Prix, it is not. It is very, very late. The gates open at about 6 am, and the best seats are claimed then in general admission (I’ll go into this a bit more on my next post). We got there closer to 9:45 am, so on Sunday had seats about 4 rows back from the top of the terraces. This is a big upside for camping, as you can be there when you want, and can also stay there longer – I would have loved to stay until late, especially on the Sunday when the Grand Prix Party is on – I wish I could have made it! Maybe next year…

The atmosphere was brilliant, the racing was fantastic, and the whole time spent at the track was brilliant. I will again post in more detail on this next post, where I’ll have some pictures, videos and sounds. As a side note, the sight and sound of an F1 car is astonishing – they are elegant and sleek in looks, and the sound made is beautiful (as you can tell, I love F1).

The hotel itself was average overall – the rooms were very good: comfortable, modern, clean and well equipped, but the service of the staff was poor. First, I had to give a £50 imprint of my card at check-in in case I used any ‘extras’. When I enquired as to what these were, the receptionist answered with ‘they are extras’ they finally told me what they were with an attitude. Not the best of starts, and it seemed as though the travel company weren’t aware of this either, as the rep was complaining. Breakfast on the two mornings was far from great too.  A cooked breakfast was only got by collaring a waiter, and for the most of the time, there were no knives, forks, cups, or glasses. The cooked breakfast itself wasn’t too great really, so overall, it was a bit of a shame, as the hotel could be good, if the service was improved.When checking out, I asked for a receipt of my £0 room charges, for proof in case they tried any funny business. I was greeted with another bad attitude from the receptionist, so it went from ‘Can I have…’ to ‘I want a ‘ – I was not happy.

Rant over, the time spent at the track overruled this – I would have slept there if I could have! Anyway, it is getting a touch late now, and I do have work tomorrow, along with a spot of car hunting, which brings me to my final point – I passed my driving test on Thursday! I am really pleased with this, and hope to get a car as soon as I can. Until my next post, which should be very soon, goodbye!

Tags: , , , , , , , ,

No Comments

The Future

Jun 14

Posted by Matt in Plans

What a pretentious title. Anyway, what will become of www.tangohead.co.uk? Well, over the next few weeks, alongside posting, I will be modifying it to my needs, and getting it just how I like it. This will hopefully allow me to learn some PHP, JS, and CSS, along with reinforcing my rather weak HTML knowledge. Once I have got that done, I plan on having this blog as a sub-section of my site, with a variety of random stuff taking up the rest of the space – we’ll see what ends up there. Anyway, that has kind of ‘fleshed out’ my plans, so lets see what happens!

Matt

I’ll make a more useful post soon, I swear…

Tags: , , , , ,

1 Comment

Hello world!

Jun 14

Posted by Matt in General stuff

Hi there!

I’ve finally got back into blogging, but this time have bought a domain. First, I must thank Dan Mercer though, for allowing me to use his hosting. It’s a great help indeed. Other than that, I welcome you to my blog, and I hope you will enjoy my upcoming posts!

Matt

5 Comments