Why Candy Crush is so difficult – and popular?


【APP遊戲】Candy Crush Saga
Candy Crush Saga (Photo credit: Albert.hsieh)

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, there are no obvious “solutions” to the “problems” you face as a player.

Toby Walsh of the University of South Wales has published a paper than shows that the “problems” of Candy Crush are in the class of what is known as “NP”.

NP problems are those which we do not know in advance what the solution is, but for which we can relatively quickly check that the solution applied is correct. In fact NP problems are at the core of internet (and most serious) encryption – internet encryption is difficult to crack in an attack but decryption is easy if the keys  are known.

NP problems are in distinction from “P” problems for which we know, in advance, both a procedure to solve the problem and to check our answer is correct. The “P” here stands for “polynomial time” – meaning we can tell how long the problem will take to solve at the start because it is some multiple (a polynomial) of its initial complexity – long division by pen and paper is a good example from everyday life – we know how to do it and we can instinctively tell how long it will take just by looking at the length of the numbers we are dividing.

Some – but not many – mathematicians believe that NP problems are really just P problems in disguise – it is just that we have not just discovered the way to solve them. In fact it can be shown that if we could find a means of solving a special class of NP problems known as “NP complete” problems then we could solve all NP problems. But most mathematicians believe that NP problems are inherently not amenable to being solved by simple procedures in polynomial time, while yet others think that such a procedure might exist but that the polynomial will be so large that we might see little advantage in cracking the problem.

In the meantime a whole industry has arisen to offer software to solve – though heuristics (informed guesses) and approximations some of the most important NP problems – such as scheduling school or train timetables.

It’s probably not an unreasonable assumption that people like Candy Crush precisely because it is so difficult and because, it would appear, no one is ever going to come up with a way of quickly solving the problems. We can get better by playing more – so that our heuristic sense of what works increases, but no one is going to emerge as an invincible player – because that is inherently not possible. Probably.

(If you want to know more and are not afraid of some maths, then P, NP, and NP-Completeness: The Basics of Computational Complexity might be worth having a look at.)

Enhanced by Zemanta

More on P and NP


English: Euler diagram for P, NP, NP-Complete,...
English: Euler diagram for P, NP, NP-Complete, and NP-Hard set of problems. (Photo credit: Wikipedia)

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 NP” in my paper “P versus UP” which is published in IEEE,

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6272487

I’m working in that problem as a hobby since I graduated. I sent a preprint version in Arxiv with the intention of find some kind of collaboration. I also tried to find help in another blogs. But, finally I decided to sent to a journal of IEEE a new version which differs of the preprints in Arxiv that I withdrew because it had some errors. Then, I waited and after a revision in a IEEE journal I was published in 17th August 2012.

However, I wrote this paper in Spanish and I had the same version in English. So, I decided to sent again to Arxiv, but they denied me that possibility, therefore, I used a pseudonymous. I also uploaded other papers with that name which are not so serious but reflect the work that   I’m doing right now as a hobby too.

I love Computer Science and Math. I’m working right now in a project so important as P versus NP, but I do all this as a way of doing the things that I like most although my environment doesn’t allow me at all. I also tried to work with other scientists which have invited me to work with them since I published my paper in IEEE. Indeed, I don’t want to be annoying with my comments, I just searching the interchange with another people who have the capacity to understand my work, that’s all.

Good Luck

Frank’s website is here: http://the-point-of-view-of-frank.blogspot.com/

An NP-complete problem from the world of embedded computing


English: Euler diagram for P, NP, NP-Complete,...
English: Euler diagram for P, NP, NP-Complete, and NP-Hard set of problems. (Photo credit: Wikipedia)

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 solve them exists. For instance, solving (i.e., finding the value of x where the formula evaluates to zero) x – 2 is a P class problem. NP (not P) problems are much more interesting – these are problems for which an algorithm exists but which is unknown at the time the problem is posed. In the worst case the only way of solving the problem may be to try all the potential algorithms until we find the one that solves the problem. That said, once a potential solution is found it can be verified ‘simply’ (i.e. in polynomial time). It is not known if, in fact NP problems (such as drawing up school timetables or cracking internet public key encryption) are really P type problems after all and we just have not found the solution or are permanently excluded from ‘simple’ (P) solutions. A class of NP problems called ‘NP complete‘ are those that, if shown to really be P class problems, would indicate P=NP. Most, but not all, mathematicians think, in fact P!=NP.

So, here’s the problem. It sounds simple, but as it is NP, it’s not! (I got this from Making Embedded Systems: Design Patterns for Great Software)

You have a micro controller with a timer of fixed 4MHz frequency and two 8 bit registers, a and b, such that (a) counts ticks and (b) is a match register that triggers an interrupt when the count register matches the tick count stored and a 16 bit prescaler (that allows the scaling of the ticks e.g. – if set to 2 then twice as many ticks are required to trigger the interrupt).

So how can you set the match and prescaler to work for an arbitrary frequency? Sounds like it should be easily algorithmically managed, but it’s not.

Reflections on the riots: part one


AddRoundKey operation for AES
Image via Wikipedia

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 short political observations: firstly, that disrespect for the law and contempt for order are not new things in London. If you read Albion’s Fatal Tree you will see that there have long been many in the capital who have made their at least part of their livelihoods from criminality and who celebrated their fellows. Pretending that recent events represent some terrible breakdown in ancient respect for authority is ahistorical.

And, before people start to say it is the fault of rap music or other “alien” influences, do they remember this? Perhaps the Fast Show is the real cause of the disorder?

So, that over, what is the science point? Well, it was consistently reported during last week’s disturbances that the looters were sharing their intelligence through BlackBerry smart phones, specifically through “BlackBerry Messenger” (BBM). Given that the UK has one of the most sophisticated signals intelligence set-ups in the world at GCHQ, the fact that the police were clearly left in the halfpenny seats by the looters suggests to me that nobody there has yet proved that P=NP or developed an algorithm to crack the one way functions used to  encrypt the BBMs.

According to Wikipedia Blackberry encrypt everything with “Advanced Encryption Standard” (AES). A brute force attack on this would, on average, require 2^{255} attempts (for the 256 bit encryption), so that is not a practical option (eg the universe is very roughly 4^{17} seconds old).

Now, it could be that the US government has cracked this thing and just refuses to tell even its closest ally (I dare say the name Kim Philby is still spat out in various places), but my guess is that AES is safe, for now.

As I have said before that is probably a pity: while a world where P=NP would be one where internet commerce was broken, it would also be one with many compensatory benefits.

“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 P = NP question.

It’s an odd statement for a computer scientist to make – most numbers are transcendental numbers and so are fundamentally incomputable: for instance there are \aleph_{0} (aleph null – the smallest of Cantor’s hypothesised infinities) transcendental numbers between 0 and 1 (or between any range of integers).

But besides that oddity it is actually a very good article – calling the world where P = NP Algorithmica – “the computing nirvana”.

I have written before of how much I hope we do live in Algorithmica, though the consensus is we live in a world of NDAlgorithmica (ND for non-deterministic).

The article’s beauty is that it also examines the states between the two: what if, for instance, we discovered that the class of P problems were identical to the class of NP problems but that we could not find the P algorithm, or that the P algorithm was of such a degree of complexity it “would not amount to a hill of beans”?

Cardinality of strings … 2


Some NP-complete problems, indicating the redu...
Image via Wikipedia

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 represented by a finite binary sequence called a string.”

Although 15 pages later writes of “the set of all strings” I am now assuming he means in the sense he first used…

But I did not have the heart to not post my message as I worked on it for a little bit.

Cardinality of the set of all strings


Oded Goldreich
Image via Wikipedia

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 myself last week and bought a copy of P, NP, and NP-Completeness: The Basics of Computational Complexity which I am now attempting to read between dozes in the garden (weather in London is fantastic). The book is written in a somewhat sparse style but even so is somewhat more approachable that many texts (the author, Professor Oded Goldreich, rules out using “non-deterministic Turing machines“, for instance, saying they cloud the explanation).

But in his discussion of (deterministic) Turing machines he states:

the~set~of~all~strings~is~in~1-1~correspondence~to~the~natural~numbers

Is that right? (Serious question, please answer if you can).

Surely the set of all strings has the cardinality of the reals?

If we had a set of strings (0,1)^* like this:

1000000....
1100000....
1110000....
1111000....

and so on…

Then surely the standard diagonalisation argument applies? (i.e. take the diagonal 1111111.... and switch states of each member – 000000... and this string cannot be in the original set as it is guaranteed that for the i^{th} member of the set, the with elements \alpha_{1 ... \infty} , \alpha_{i} will be different. (See blog on diagonalisation.)

In Naughton’s book he makes (the very valid) point that students of the sciences are generally taught that when their results disagree with the paradigm, then their results are wrong and not the paradigm: so what have I got wrong here?