# 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.