Candy Crush lies at the boundary between easy and hard.

Hard Solutions, Easy Checks

In our analysis of Candy Crush, my collaborators and I started with the most famous class of computationally hard problems, called NP for “nondeterministic polynomial time,” the “time” part of the term indicating how long these problems could take to solve. NP contains all the problems for which, if you give me a solution, I can quickly check that it is a correct answer, in a time that is just a polynomial function of the size of the problem. However, finding the solution in the first place appears to be computationally challenging. Many well-known math problems—such as determining whether a complex logical formula can be satisfied, or whether a graph can be colored so that neighboring nodes have different colors—belong to this class of computationally hard problems.

Beneath the NP class, in terms of complexity, we have the class P of computationally “easy” problems. In this case, P stands just for polynomial. P contains problems such as sorting a list or finding a record in a database. The time it takes for an efficient computer program to solve such problems is short, even in the worst case. Mathematically, the runtime of a problem in P is a polynomial that scales to the size of the problem. For example, one well-known sorting algorithm, BubbleSort, repeatedly “bubbles” the next largest item to the top of the list like a competitor in a potato race. This process takes a time that grows as the square of the size of the list to be sorted. Even if we doubled the size of the list, the algorithm would take four times as long in the worst case. This worst case is when the list is in reverse order and every item must bubble past every smaller item. If the list is not in reverse order, the algorithm will stop even more quickly.

Above NP in complexity, we have problems that are extremely hard computationally. There are even problems above NP for which our standard model of computation, the one that all our computers implement, is inadequate. For such problems, there is no computer program that is guaranteed to stop and return an answer. These examples fall in the so-called undecidable class of problems. This class includes such questions as deciding whether a computer program will stop rather than run forever in some loop, which computer scientists call the halting problem. Alan Turing, one of the fathers of computation, proved that the halting problem is undecidable. No computer program exists that can both decide whether another computer program halts and is itself guaranteed to halt, therefore making it a really, really hard computational problem.

NP lies right at the boundary between easy and hard. Within NP, we have many challenging problems such as how to route trucks to deliver parcels, roster staff in a hospital, or schedule classes in a school. It turns out that winning Candy Crush falls into this category as well. Any one of these problems can be reduced to any of the others. In this sense, they’re all equally as hard.

Unfortunately, the best computer programs we have for problems in NP have a runtime that grows dramatically as we increase the size of the problem. On my desktop computer, I have a program that takes a few hours to find the optimal routing for 10 trucks and to demonstrate that this solution was the best possible. But for 100 trucks, the same program would take more than the lifetime of the universe. Mathematically, the runtime of my program is an exponential of the size of the problem.

And exponentials quickly grow very large, as exemplified in the classic fable where a vizier wins any prize he wants from a sultan, and asks for one grain of wheat on the first square of a chessboard, then to have it doubled for each subsequent square. So there’s one grain of wheat on the first square, two on the second, four on the third, and so on. On the 64th and final square of the board, you would need 18,446,744,073,709,551,615, or more than 18 quintillion, grains of wheat. That’s approximately the amount of wheat produced worldwide in hundreds of years. Exponentials quickly sneak up on you.

Although computer scientists widely agree with my statement that NP problems are on the boundary between easy and hard, for any specific problem there is no way to know for sure which side it lies on. . . .The best computer programs we currently have take exponential time to solve problems in NP. But we don’t know if there’s some exotic algorithm out there waiting to be discovered that will solve problems in NP efficiently, in polynomial time. (Mathematicians abbreviate this question as “Does P=NP?”) In fact, this is one of the most important, famous open problems in mathematics today. The Clay Mathematics Institute has even offered a $1 million prize for the answer to this question. The prize remains unclaimed since it was first offered in 2000.

In the most recent poll on whether P=NP is true, 83 percent of computer scientists thought that P was not equal to NP. That is, they think there are no efficient algorithms for solving problems in NP and there never will be. Another poll of computer scientists was used to decide what to call problems that are as hard to solve as those in NP, whether or not they are in this class. The final name chosen was the rather prosaic NP-hard. But the poll did demonstrate a refreshing and geeky sense of humor: Some alternative write-ins were NP-impractical, NP-tricky, and NP-hard-ass.

The idea of problem reduction is central to the P=NP question. If we did find an algorithm that could solve any one of these problems in NP efficiently, then we also could solve all of the problems in NP efficiently. The world would be a very different place if this outcome ever happened. On the plus side, we’d be able to go about our lives with better time management, optimally routing trucks, timetabling flights, and scheduling staff to save money (and routinely winning at Candy Crush). However, we depend on other tasks, such as cracking codes, to be computationally challenging so that our passwords and bank accounts stay secure. Computational complexity can be a blessing as well as a curse. We want to make it provably hard for hackers to compute how to decrypt messages. Equally, we need to be able to encrypt those messages easily.

This example might remind you of the definition of NP: problems where it is easy to check answers but hard to find them. Cryptography is all about putting computational barriers in the way of the bad guys. If such barriers disappear, our modern world would be in big trouble.

How is Candy Crush Saga like an electrical circuit?

At the author’s website, you will find a video of a Candy Crush board illustrating an electrical circuit (bottom of page 3. To read page 3 of the actual article, watch the video, and continue the actual article, click here.