Monday, April 1
12:30-1:20pm
JCL 390
Super Mario Bros is NP-hard
Welcome back to the spring quarter! This is an announcement for the Pizza Seminar, a grad student initiative where PhD students present to each other over a free lunch. Talks can be a chance to present something from your research of general interest, practice a conference presentation, or just tell us about something interesting.
The talk will take place in JCL 390 on Monday, April 1. Alan Chang will present some fun math about classic videogames,
Super Mario Bros is NP-hard
Abstract: First we’ll review some complexity classes. Then we’ll show that certain decision problems are NP-hard. For this talk, it would be best if you are familiar with the 1985 video game Super Mario Bros. If you have never played it, you can borrow it from Mansueto. Alternatively, you can play the game online… If Super Mario Bros. is too easy for you, try Cat Mario instead.