New "Candy Crush" Game Show Spotlights Nondeterministic Polynomial Time


Like Angry Birds and Fruit Ninja before it, Candy Crush is about to evolve into more than a mobile game. But instead of getting the big screen treatment like its forebears, Candy Crush is being developed as a CBS live-action game show.

Executive producer Matt Kunitz (the guy behind of Fear Factor) is hoping that the 93 million people who play Candy Crush will also want to watch, per The Hollywood Reporter, “Teams of two use their wits and physical agility to compete on enormous interactive game boards.” But the actual Candy Crush contestants will have to have a lot more than a love of the game to win; they’ll need to understand some very complex math.

In 2014, Australian artificial intelligence researcher Toby Walsh published a paper arguing that Candy Crush is a puzzle that falls into a class of computationally difficult mathematical problems that are called NP, which stands for “nondeterministic polynomial time.” NP problems are the ones where a correct answer can be checked in, as Walsh describes, “A time that is just a polynomial function of the size of the problem.” By qualifying as NP-hard, Candy Crush is in the same category as problems like figuring out how to route trucks to deliver packages or scheduling classes in a school. These are problems that become more difficult to solve as the size of the input is increased.

As Jacob Aron of New Scientist explains, to figure the mathematical component of Candy Crush Walsh “created arrangements of candies that are equivalent to logical statements in maths puzzle called the Boolean satisfiability problem, which asks whether a string of logical statements are compatible or will contradict each other.” This circuiting led Walsh to believe that Candy Crush is designed in a way that it’s just as hard to solve as any other problems are in NP — which is to say, very very hard.

The bad news is that scientists don’t know of a sure-fire way to solve NP-complete problems, so there’s no Price is Right style cheat codes yet.