Thursday, March 13, 2014 ... Deutsch/Español/Related posts from blogosphere

Candy Crush is \(NP\)-hard

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)

Difficulty makes Candy Crush so addictive (Phys.ORG)
What he proves in the paper is that this would-be childish game is \(NP\)-hard!

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, hard

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.
He 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\).

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.

Add to Digg this Add to reddit

snail feedback (13) :

reader rsala said...

A while back I kidded you about being banned from Scott's blog when your response to one his posts didn't appear quickly enough ... now I see that it has actually come to pass!

Scott could probably tolerate you schooling him in QM, but in his own field ... not so much. From my perspective, as someone with no background in complexity theory, your observation that, "if the problems are all equivalent, they are really the same problem", made his parable of the frogs look rather pointless.

As someone who's been on the wrong side of you frankness, I much appreciate it to Scott's snarky ad hominem attacks. Also his frequent use of appeal to authority in his arguments suggests a lack of confidence on his part.

reader Curious George said...

Is P = NP? Yes or no? People can get quite religious in their belief, and they know that no one knows (yet). Big Endians vs Little Endians again (h/t Jonathan Swift).

reader Roger Schlafly said...

Aaronson banned me from his blog also. My sin was that I expressed skepticism about quantum computing without actually having proof that it is impossible.

reader anony said...

I just wish people would stop sending me those candy crush requests on fb

reader Casper said...

To the Dalai Lama, the Church of Homophobia is always open and new members welcome. We have a full deprogramming service available.

reader Peter F. said...

Hej Lubos! t's a pity you are not capable of being sleazy just for as long as it would take you to scoop home this contemptible prize!
I simply just think you deserve - and want you to get - that sum of money! :-]

reader Luboš Motl said...

Yours is not a sin, just complete stupidity.

reader Luboš Motl said...

Thanks a lot, Peter. But there is a sense in which I really stopped caring about money, mostly, well, to the extent that was expected from Mother Teresa and others. ;-)

reader Roger Schlafly said...

You and Aaronson sure like name-calling. He says that you really don't have a clue about complexity. Until someone decides P=NP it could go either way, and until someone demonstrates a quantum computational speedup, it may not be possible.

reader deepest_thought said...

Now a new proof has been announced by other researchers, pointing out some weaknesses in the assumptions of the previous one and proving the "hardness" of many other games like Bejeweled. They got even further by providing the possibility to "play their proof":

reader Dave Kinard said...

It's insidious. To unlock the higher levels, the game makes you send fb requests to non-players inviting them to play. Viral marketing in the extreme.

reader skyje said...

Nice Share, Candy Crush is now featured on fillapps:

reader Luboš Motl said...

Is it some spam? Candy Crush is about 1,000 times more famous than Flilapps, so you're talking about a tail wagging the dog.

(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) })(window,document,'script','//','ga'); ga('create', 'UA-1828728-1', 'auto'); ga('send', 'pageview');