Tag: P==NP
-
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…
-
The world’s fastest computers
Every six months or so a list of the world’s fastest computers is published in the “Top 500” list. Except it is not. For surely the world’s fastest computers are in the hands of the NSA, GCHQ and whatever the French and Chinese equivalents are (I think we can probably discount the Russians for now)?…
-
Even if P=NP we might see no benefit
Inspired by an article in the New Scientist I am returning to a favourite subject – whether P = NP and what the implications would be in the (unlikely) case that this were so. Here’s a crude but quick explanation of P and NP: P problems are those that can be solve in a known…
-
Have we reached “peak silicon” and what can we do about it?
Moore’s Law states that the number of transistors that can be squeezed into a given slice of silicon doubles every two years (or 18 months) – something I wrote about recently and where I declared “More transistors means greater speed, more and cheaper memory and so on … ” Except, maybe not. As the graph…
-
Reflections on the riots: part one
This is a blog about computing (along with some maths and science) – and not about politics, and having disciplined myself to stick to that for the last nine months, I intend to keep it that way, even as I write about the biggest political event of the year. But I will allow myself two…
-
“Basically, you would be able to compute anything you wanted”
The quote that forms the title here comes from Lance Fortnow, a computer scientist at Northwestern University, in an article (here – subscription required) in the current edition of the New Scientist on the question. It’s an odd statement for a computer scientist to make – most numbers are transcendental numbers and so are fundamentally incomputable:…
-
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…
cartesian product ... stuff about computing mostly 