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.

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.