You are here

The Power of Problem Reduction

Writing for American Scientist, Toby Walsh explains not only how he proved that Candy Crush is a mathematically hard puzzle to solve but also what this implies for more practical problems.

"If we had an efficient way to play Candy Crush," writes Walsh, "we would have a provably efficient way to route trucks, roster staff, or schedule classes. Alternatively, if we had an efficient way to way to route trucks, roster staff, or schedule classes then we would have an efficient way to play Candy Crush. That’s the power of a problem reduction."

Read the article.

Start Date: 
Tuesday, October 28, 2014