A Crushing Problem A computer scientist analyzed the complexity of a popular mobile game, Candy Crush, and found that it is NP-hard — that is, it's hard to solve, but answers are easy to verify. Manon Bischoff reports on the finding for Scientific American. Complexity theory helps to clarify what kinds of problems can be solved easily by classical computers, and how quantum computers can solve some of the harder problems. In 2018, Kevin Hartnett wrote a short guide to the different complexity classes for Quanta. Cut to the Good Stuff What's the fairest way to split a cake? When dividing between two people, the "I cut, you choose" method works, but among more people, the division gets more complicated, Stephen Ornes writes for Science News. The cake-cutting problem is a deceptively tricky one, and mathematicians have grappled with it for years. Back in 2016, Erica Klarreich reported for Quanta on a new algorithm that fairly splits a cake among any number of people. | |