Computational Complexity Classes, P vs. NP, and the Hardness of Pokemon
In this video, Alec Friedman presents a proof on the computational complexity of the popular Nintendo video game Pokemon. First Alec will introduce the topic of complexity classes and talk about one of the most debated and unanswered questions in computer science: whether or not P=NP. Alec will then introduce the notion of a reduction, and use a reduction from the problem 3CNF-SAT to prove that Pokemon belongs to the complexity class NP-Complete.
Project Members: Alec Friedman