  We classify the computational complexity of the popular video games Portal
and Portal 2. We isolate individual mechanics of the game and prove
NP-hardness, PSPACE-completeness, or (pseudo)polynomiality depending on the
specific game mechanics allowed. One of our proofs generalizes to prove
NP-hardness of many other video games such as Half-Life 2, Halo, Doom, Elder
Scrolls, Fallout, Grand Theft Auto, Left 4 Dead, Mass Effect, Deus Ex, Metal
Gear Solid, and Resident Evil.
  These results build on the established literature on the complexity of video
games.
