Pac-Man : NP-Hard
Boulder Dash (First Star Software, 1984) is NP-hard. Deflektor (Vortex Software, 1987) is in L.
Prince of Persia (Brøderbund, 1989) is PSPACE-complete.
Tron (Bally Midway, 1982) is NP-hard.
(via Pac-Man Proved NP-Hard By Computational Complexity Theory - Technology Review)
