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… Read More A further suggestion that P!=NP
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… Read More An NP-complete problem from the world of embedded computing
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… Read More Possibly the most important news you will read this year
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… Read More What if P = NP?