Complexity theory Pac-Man Proved NP-Hard by Computational Complexity Theory Sharon D. Cole January 26, 2012