Seminar Fun with Reductions

We say problem A reduces to a problem B  (equivalently,  you can say A is at least as easy/hard as  B when a solution to B would yield a solution to A.

Reductions are ubiquitous in Computer Science. In the past few decades, thousands of natural problems from disciplines as varied as evolutionary biology to statistical physics have been proven to be NP-hard An incredible consequence of these reductions is that if one of them is easy, then all of them are easy -- this is the famous question of if the complexity class P is different from NP. Identifying when a problem is hard is an indispensable tool in the arsenal of any computer scientist. In this seminar, we will study exactly such techniques that allow us to learn about the limitations of various algorithmic techniques, and provide us with techniques for proving hardness.

We will see that many popular games (Mario, Tetris, Minesweeper) are NP-hard. (It also turns out that 2-player games like Go and Chess are even harder than NP). The precise complexity of some of these games/puzzles are still open and solving them might lead to publishable papers.