In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation This is a strange little book – and while I am happy to recommend it, I am not really clear in my own mind what sort of a book it is meant to be. A popular description of a famous problem in the… Read More In Pursuit of the Traveling Salesman
If the evidence of my commute is any guide then Candy Crush Saga probably uses as much compute cycles as any other program in London – it is wildly popular. And if you are player (I am not) then you shouldn’t be surprised or disappointed if you actually struggle with it – because, in fact,… Read More Why Candy Crush is so difficult – and popular?
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… Read More Even if P=NP we might see no benefit
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
Vladimir Romanov has conceded that his published “proof” of P=NP is flawed and requires further work. So, it seems internet commerce is safe for now. But Romanov is not throwing in the towel: Thank you for your attention to my work. You’d better suspend your investigations. A shortcoming possibly exists in the filtration procedure which… Read More No proof of P=NP after all (yet?)