![]() If you can classify a problem by how hard it should be to solve, you know what kind of computing power to throw at it-and even if it’s worth trying to solve at all. And if you can show the reverse, that the second problem can also be reduced to the first problem, then in some sense the two problems are equally as hard as each other, and take a similar time to solve.ĭetermining the difficulty of a problem is a fundamental tenet of mathematics. The second problem can’t be easier because you must be able to solve the first problem with a computer program that can solve the second problem. If the problem you started with was hard, then the problem you map onto must be at least as hard. At its heart, this concept arises because computer code is versatile: You can use the same type of code to solve more than one problem, even if the variables differ. This idea maps one problem onto another, or as computer scientists like to say, it reduces one problem into another. To prove this point, I needed to call upon one of the most important and beautiful concepts in the whole of computer science, the idea of a problem reduction. In a recent proof, I demonstrated that Candy Crush is a mathematically hard puzzle to solve (the paper is available at ). Surprisingly, the game holds a lot of interest for researchers as well: It offers insight into one of the most important open problems in mathematics, as well as into the security of computer systems. ![]() That’s not bad for a simple game of swapping candies to form chains of three or more identical pieces.Ī big part of the appeal of Candy Crush for players is that there are complex underpinnings to the seemingly simple puzzle. Largely based on this success, its developer, Global King, listed recently on the New York Stock Exchange in an initial public offering valuing the company in the billions of dollars. It has been downloaded and installed on phones, tablets, and computers more than half a billion times. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |