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…
-
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…
cartesian product ... stuff about computing mostly 