Skip to main content


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

Find the program that fits your life.

Learn about our coding, cybersecurity, and data analytics bootcamps offered on full-time and part-time schedules.