Tag: NPcomplete

In Pursuit of the Traveling Salesman
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 […]

Why Candy Crush is so difficult – and popular?
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, […]

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

No proof of P=NP after all (yet?)
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 […]