Candy Crash [Saga] is currently the most popular game on Facebook. Play it quickly here. You may also download it for Android and iOS along with hundreds of millions of users.
You may permute two adjacent fruits in a grid. Such a move must create at least a triplet of identical fruits in a row or column and they disappear which is a good thing. I've spent hours with games based on the same idea although not this particular one.
Toby Walsh from a university in Sydney turned this popular software into a piece of interesting computer science by offering a non-trivial proof.
The preprint and the popular account by the same author are here:
Candy Crush is \(NP\)-hard (arXiv)What he proves in the paper is that this would-be childish game is \(NP\)-hard!
Difficulty makes Candy Crush so addictive (Phys.ORG)
What does it mean?
The \(NP\)-complete class is the intersection of \(NP\) and \(NP\)-hard. The mutual relationships between the sets simplify if \(P=NP\) which may be true or false.
It means that it's at least "as difficult to solve" (with difficulty counted as the number of operations) as the hardest problems in \(NP\), the class of problems whose solutions may be demonstrably verified polynomially quickly (which may imply but doesn't have to imply that they may also be solved polynomially quickly – the class of problems solvable polynomially quickly is called \(P\)). Note that according to the diagrams above, many \(NP\)-hard problems are probably outside \(NP\) (they are strictly harder than \(NP\)).
The fact that the popular fruit game is \(NP\)-hard means that problems in the \(NP\) class may be "reduced" to a specific task (generalized game of a sort) in Candy Crush. Because other \(NP\)-problems have been reduced to 3-SAT, the computer scientists' most favorite \(NP\) problem asking you to verify whether a proposition (a binary function of binary variables) is a tautology – with some restrictions on the form of the composite proposition that reflect the number 3 in the name – it follows that Walsh had to show the "speedwise equivalence" of 3-SAT and Candy Crush.
Normally, people would be showing that other \(NP\) problems may be reduced to the 3-SAT – trying to pretend that 3-SAT is more fundamental. (It is of course equally fundamental as others; which you prefer is mostly a matter of taste.) However, Toby Walsh would reduce 3-SAT to something even more "fundamental": a childish game with fruits. ;-) He showed that if you are asked to solve a 3-SAT problem, you may sort of create a Candy Crush problem and ask an experienced child or adult player to solve this one. The solution may be translated to a solution of the original 3-SAT problem.
I hope that the proof is OK but I haven't verified it.
Note that it's not really "terribly hard" for a computer to play Candy Crush really well. In many cases, it is able to figure out how to play it optimally. The problems only arise in the "worst case scenarios" when it may become harder to find the right solution. You shouldn't forget about this observation when you hear the hype that \(P=NP\) would lead to far-reaching practical consequences and music fans would start to compose ingenious compositions like Mozart (even Walsh tries to spread this hype although he also says the right sensible things about these matters). They wouldn't start anything like that. In fact, the real world wouldn't substantially change at all because for practical purposes, "almost perfect" solutions may be quickly calculated even today.
What's funny is that according to his text in Phys.ORG, Toby Walsh fully agrees with your humble correspondent – and disagrees with Scott Aaronson – in the statement that \(P\neq NP\) is no more likely to be true than false. The question is open. Walsh writes:
Deciding between 'easy' and 'hard' is, um, hardHe doesn't say that "computer scientists believe that \(P\neq NP\), as Scott Aaronson does". He impartially says that the \(NP\) problems are on the boundary of "easy" and "hard", so it's comparably likely that \(P=NP\) or \(P\neq NP\).
Surprisingly, while computer scientists believe problems in \(NP\) are on the boundary between easy and hard, they don't actually know on which side they are.
The best computer programs we have take exponential time to solve problems in \(NP\). But we don't know if there's some exotic algorithm out there that will solve problems in \(NP\) efficiently – and by efficiently, we mean in polynomial time.
In fact, this is one of the most important open problems in mathematics today, the famous \(P=NP\) question. The Clay Mathematics Institute has even offered a US$1 million prize for the answer to this question. The prize remains unclaimed since it was first offered in 2000.
The idea of problem reduction is central to the \(P=NP\) question. If we did find an algorithm that could solve any problem in \(NP\) efficiently then, by exploiting the idea of problem reduction, we could solve all problems in \(NP\) efficiently. The world would be a very different place if this ever happened.
On the plus side, we'd be able to go about our lives more efficiently, routing trucks, timetabling flights, and rostering staff to save money, but the absence of efficient algorithms to do various tasks such as crack codes is also required to keep our passwords and bank accounts secure.
Incidentally, Scott Aaronson allowed 350 comments in his thread about \(P=NP\) which said that it was inspired by your humble correspondent. Many of the comments question what I am saying, sometimes in a very malicious and personal way. But I wasn't allowed to respond to the last 200 comments or so even though the answers I wrote were totally clean, impersonal, and in many cases, they fully settled the concerns of other readers of Aaronson's blog.
Aaronson has manipulated himself into constantly saying some things that are just mathematically indefensible and he is afraid to admit that he has been wrong about rather fundamental things of his field for years. And he is afraid to post my comments because they make it rather obvious to other readers that his reasoning has been irrational and that my approach to the complexity theory is more professional than his attitude.
This guy is funny, and sort of smart, but he just doesn't have any traces of the scientific integrity. So he prefers to allow often anonymous idiots (and himself) to post malicious libelous personal comments directed against your humble correspondent over factual and sometimes waterproof technical comments if they would show that he's been deluded and he's still deluded.
At any rate, censorship and intimidation are the only arguments that \(P\neq NP\) must almost certainly hold and they are very weak arguments.