Super Mario Bros is NP-complete (Joint Seminar w/ Applied)

Matthew Taylor

Frank Adams 1,

The "P vs NP" problem is one of the Millenium Prize problems and probably one of the most important unsolved conundrums ever.
 
The problem statement is fairly simple: if the solution to a question can be verified quickly, can that question be solved quickly? The philosophical implications, however, are potentially massive. In the words of MIT's Scott Aaronson, if the answer is yes, then "everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss".
 
A special set of problems, labelled "NP-complete", form a major part of work in the field. I'll be explaining what these are, after an introduction to P vs NP (no prior knowledge required!). I'll then explain how Super Mario Bros, Pokemon and several other games were proven to be NP-complete in 2012. Find an efficient way of solving them, and you'll be rich!
Import this event to your Outlook calendar
▲ Up to the top