Skip to content
Hallway
0:00 / 0:00

#np-completeness#pspace-completeness#complexitytheory

16. NP and PSPACE Video Games

MIT OpenCourseWare

6.5M subscribers • 37 videos on Hallway • University channel

YouTube
  • Recommended by 2 people: 2 in engineering communities.
  • Presented by Erik Demaine, Professor at MIT
  • May be out of date. Uploaded 11 years ago, in an area where tools change fast.

Advanced. Deep dive for people who know the field.

8.1K views11 years ago2 recommendations

Computer scienceGame developmentComputation and complexityAlgorithmsGame design

Erik Demaine proves the NP-hardness and PSPACE-completeness of various classic video games, explaining algorithmic lower bounds.

MIT 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs, Fall 2014 View the complete course: ocw.mit.edu/6-890F14 Instructor: Erik Demaine In this lecture, Professor Demaine proves the NP-hardess of various video games. License: Creative Commons BY-NC-SA More information at ocw.mit.edu/terms More courses at ocw.mit.edu

Why it's here

2 people recommend this

What people say. Recommended for learning about NP-complete reductions and complexity proofs using video games as examples.

u/BenBalsin r/compsci • Recommends

On “Resources or approaches for making NP-complete reductions”

Also, try to get interested in it. Find problems that scratch an itch for you. Like gaming? Show that Super Mario Maker ist NP-complete! I wrote on why Minesweeper is NP-complete at a level that is definitely accessible to a student. You can even try to prove that yourself! It's not that hard. If you want to challenge yourself a bit, take a look at this paper that proves the NP-completness of many 3D video games such as Portal or GTA. If you need to practice for an exam, get a list of student-level problems and just do them all. I can recommend the problems in chapter 7 of *Introduction to the Theory of Computation* by Michael Sipser. If you like videos take a look at the following 1. A…
2View on Reddit

u/Limettengeschmackin r/compsci • Recommends

On “Article of Mario NP-hardness?”

Throughout this lecture he even presents a proof that it is PSPACE complete. Timestamp is 1:01:00.
1View on Reddit