Tag: 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 […]

Possibly the most important news you will read this year
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 […]

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 […]