Tag Archives: polynomial time

A further suggestion that P!=NP


There are a class of mathematical problems known as “P”: these can be solved in “polynomial time” or, to cut to the chase, they are problems for which we know how (algorithmically) to solve when we see them. A trivial example is -if you are given a number X, how do you calculate Y which is  X times 10. (If you don’t know the algorithm to multiply a base 10 number by 10 then stop reading this now!)

There are another class of problems – the “NP” (as in “Not P”) problems for which we know how to check if we have a correct solution to the problem, but not how to solve the problem itself. A typical example is producing the factors of a very large number created by multiplying two very large prime numbers together. If I gave you the factors you could probably verify that their product was the larger number, but if I gave you the larger number you might be here until the end of the universe trying to figure out what the factors were, as the only real way we know of (today) is to eliminate every prime number, one by one.

But, it may just be the case that “NP” problems are actually “P” problems after all, and it’s just we have yet to discover the algorithm to solve them. If we could show that NP=P in this way then we could do things like simply draw up train and class timetables instead of fiddling with expensive and approximate software tools to get these right.

But we’d also be able to crack internet encryption, which essentially relies on large numbers produced by two very large primes (public and private keys). These “one way functions” – i.e. bits of maths easy to do one way (multiply the two primes) but essentially impossible the other way – factor their product – are at the core of internet encryption.

Encryption and mathematics are deeply entwined and so communications intelligence agencies like the NSA in the United States and GCHQ in the UK are also centres of mathematical excellence – trying to break codes and, we must assume, test whether P=NP after all.

So this fascinating story about the state of encryption software in the US might suggest to us that the NSA have not been able to prove P=NP (most mathematicians think P!=NP but that is not proved either).

(The story essentially suggests that the NSA have paid to have a widely used form of internet encryption - Dual_EC_DRBG – operate like an Enigma Machine where the starting positions are always known. As with Enigma, once you had that, everything else would fall into place and what looks like a random sequence of letters is quickly converted to plain text.

Of course it could all be paranoid nonsense or even a cover to make us think that they haven’t cracked the P=NP problem (as, after all, you’d guard that secret with everything you’d got – except internet encryption!) – paying out a few million dollars to make someone think you had doctored one way functions because you could crack them no other way would be money very well spent!

An NP-complete problem from the world of embedded computing


English: Euler diagram for P, NP, NP-Complete,...
English: Euler diagram for P, NP, NP-Complete, and NP-Hard set of problems. (Photo credit: Wikipedia)

First of all – a quick explanation of P and NP. The class of problems known as ‘P’ – for polynomial (as in they can be solved in a time which is dependent on a polynomial of their complexity) – are those for which a known algorithm – a sequence of mathematical steps – to solve them exists. For instance, solving (i.e., finding the value of x where the formula evaluates to zero) x – 2 is a P class problem. NP (not P) problems are much more interesting – these are problems for which an algorithm exists but which is unknown at the time the problem is posed. In the worst case the only way of solving the problem may be to try all the potential algorithms until we find the one that solves the problem. That said, once a potential solution is found it can be verified ‘simply’ (i.e. in polynomial time). It is not known if, in fact NP problems (such as drawing up school timetables or cracking internet public key encryption) are really P type problems after all and we just have not found the solution or are permanently excluded from ‘simple’ (P) solutions. A class of NP problems called ‘NP complete‘ are those that, if shown to really be P class problems, would indicate P=NP. Most, but not all, mathematicians think, in fact P!=NP.

So, here’s the problem. It sounds simple, but as it is NP, it’s not! (I got this from Making Embedded Systems: Design Patterns for Great Software)

You have a micro controller with a timer of fixed 4MHz frequency and two 8 bit registers, a and b, such that (a) counts ticks and (b) is a match register that triggers an interrupt when the count register matches the tick count stored and a 16 bit prescaler (that allows the scaling of the ticks e.g. – if set to 2 then twice as many ticks are required to trigger the interrupt).

So how can you set the match and prescaler to work for an arbitrary frequency? Sounds like it should be easily algorithmically managed, but it’s not.

Possibly the most important news you will read this year


This an example of how a public and private ke...
Image via Wikipedia

Apparently P==NP. (So public key encryption – used for internet commerce – is broken and many more problems than we previously thought are quickly solvable).

At least that is the suggestion you can read here. Slashdot also has this here.

If it’s true then the revolution has just begun. If it’s false, well, tomorrow’s another day…

What if P = NP?


Update (5 March): read a better version here.

I admit I now going slightly out of my depth, but I will try to explain what this is about and why it is interesting.

It is known that computers can solve some problems in what is called “polynomial time“: that is to say a finite time that is proportional to a polynomial of complexity of the input. The key thing is that these problems are computable using mechanical steps (ie algorithms) in a way that is (sometimes euphemistically) described as “quickly”.

These can be simple problems – like what is the sum of the first ten integers – or more complex ones, such as creating self-balancing trees, sorting database records alphabetically and so on.

These are the so-called “P” (for polynomial time class) problems. Here’s a definition:

A problem is assigned to the P (polynomial time) class if there exists at least one algorithm to solve that problem, such that the number of steps of the algorithm is bounded by a polynomial in n, where n is the length of the input.

Then there are another class of problems which seem fiendishly difficult to solve but which it is relatively simple to prove the correctness of any solution offered. These problems can also be solved (computed) in polynomial time – ie a finite time – and they can also be computed by a Turing machine (a simple model of a computer) and so an algorithmic solution exists. It is just that one cannot tell what that algorithm is. These are said to be solvable in unbounded polynomial time – and in the worst case the only way – it is thought – that a solution can be found is through an exhaustive search of all algorithms – in other words a form of “brute force“. These are the NP (Not in class P) problems.

Now most mathematicians think that NP does not equal P and that may or may not be a good thing as much of our internet commerce relies on encryption which is thought to be an NP problem.

(In Afghanistan in 2001 US cryptanalysts seemingly brute forced a Taliban Windows NT box but it used much weaker encryption than most electronic commerce.)

But what if it were the case that all seemingly NP problems were actually P problems? There are a lot of people studying this issue – but according to the New Scientist (their Christmas edition, the first in my subscription and delivered this morning, inspired me to write this) we should expect to wait at least until 2024 for an answer (by which point the problem – first formulated in 1971 – will have reached the age at which 50% of major mathematical problems will have been solved).

Some problems thought to be NP have already been shown to be P and there was a big fuss earlier in 2010 when a draft proof of P = NP (edit: it was actually P != NP) was published (the proof was flawed). And unlike, say, Fermat’s last theorem, proving P = NP is likely to have more or less immediate effects on the lives of many of us (how would you feel if you knew that it was possible, even if not likely, that someone had developed a way to quickly crack open all your internet credit card transactions?)

Of course, proving P = NP for all problems does not necessarily mean we will have determined polynomial time based solutions for all the current NP problems out there. But I would expect it would quickly lead to the solution of a multitude of them.

And, actually, I think the benefits to humanity would be enormous. The most likely immediate effects would be in improvements in computing/operating system efficiency. fast computers for less money and/or less energy consumption would be a huge benefit. From that alone many other benefits will flow in terms of information availability and universality.