From SIPB Cluedumps
|Date: May 3, 2017, at 7:00 PM|
|Presenters: Ray Hua Wu and Jayson Lynch|
| Abstract: The question of whether the complexity class P is the same as the class NP has been the central open question of complexity theory for decades. Even a weaker question, whether P is the same class as PSPACE, is still not resolved. Yet new problems proven NP-complete or PSPACE-complete are churned out by the month. Particularly interesting problems that have been categorized as complete with respect to a complexity class include theoretically-defined extrapolations of video games. In this cluedump, we analyze the complexity of various problems in Tetris, Minesweeper, Super Mario Bros., The Legend of Zelda, Pokémon, Portal, and other video games.
Although we will try our best to explain broad ideas and big-picture points to a general technical audience, a solid foundation in basic complexity theory is necessary background for the technical details of what we present. Complexity material covered in 6.045/18.400 or 6.046/18.410, or a higher class, is sufficient; 6.006-level familiarity with complexity may somewhat suffice.