# Tag: P versus NP problem

• ## 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,…

• ## More on P and NP

From Frank Vega:   I wanted to answer you one of your comments in your post “Even if P=NP we might see no benefit“, but I saw I can’t do it anymore in that page, maybe due to problem with my internet. I was the person who claim a possible demonstration of problem “P versus…

• ## An NP-complete problem from the world of embedded computing

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…

• ## 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:…

• ## Cardinality of strings … 2

I have to make a confession. When I wrote the post below I was genuinely puzzled by the issue and what seemed to be a mistake in P, NP, and NP-Completeness, but just as I was about to press “publish” I saw that several pages earlier Professor Goldreich had stated: “We consider finite objects, each…

• ## Cardinality of the set of all strings

I finished John Naughton‘s A Brief History of the Future: Origins of the Internet – an interesting diversion, to be sure and a book worth reading (not only because it reminds you of how rapidly internet adoption has accelerated in the last decade.) By now I should be on to proper revision, but I indulged…

• ## Sexy Maths…

Paul A. Rubin – “apostate mathematician and Professor of Management Science at Michigan State University” – commented on the blog post below about P=NP and so naturally enough I had a look at his blog and the most recent item is something of a corker … “Math and Science Can Be Sexy“. In it Professor…

• ## P = NP once again

Been an interesting week here on the blog … as I said before getting on Slashdot is great as you get access to the intellect of a lot of people, and that taught me quite a bit. It’s not relevant to my course but I went to the (Maths shelves of) the Birkbeck library and…

• ## The slashdot experience

Last night I submitted a story on this blog – about P=NP – to Slashdot and today the submission was accepted and in a few hours I have had perhaps five times more visitors than in the previous two and a half months. But, thanks to WordPress.com there was no “slashdotting” – instead the site…