I am studying the complexity of Portal 2 and I would like to know if the problem has been studied before. In particular, I would be interested any reference discussing the complexity of Portal 2 and it being NP-hard/PSPACE-hard and approaches to prove such results.
I think you could show it PSPACE-hard fairly easily, as there are doors controlled by pressure switches. I'm not sure exactly what the limitations of the level design are in Portal so this may not be quite right. (As I recall most levels have one door and one switch, which is not sufficient). The HalfLife 2 engine in general seems certainly capable of making PSPACE-complete puzzles.
Some good tools for this are in this paper:
Viglietta, G. Gaming is a hard job, but someone has to do it! Fun with Algorithms 2012 http://arxiv.org/pdf/1201.4995v3.pdf
Of course, none of this uses the actual portal aspect of the game.
(An earlier version of this question asked if anyone has shown Portal 2 to be NP-hard.)
Yes, someone has done this. Portal 2 is at least NP-hard.
My friend created a proof-of-concept map showing that the ability to beat a Portal 2 level implies the ability to solve 3SAT instances:
PSPACE proof attempt of Portal 2 by reduction from TQBF
Application of section 2.2 of Gaming is a hard job, but someone has to do it! On portal 2. A direct proof of the statement: Given Portal 2 can you encode a TQBF in the game?
We disallow portals in certain parts to simplify the proof since this is allowed in the game but, we will show that if all surfaces were white then this would allow you to bypass the proof. This either changes the topology of the graph or collapses quantifiers into being the same quantifier.
Description of each gadget
I define a door as two tiles of deadly water that can't be jumped over. To unlock a door you place a block on it and the door unlocks.
- $\forall$ there is two doors activated by independent switches
- $\exists$ is modeled by a sequence of switches with blocks that are deployed and you must put a block for each one.
- Clause gadgets are cone by allowing companion cubes to travel with you to open doors. Note that in my proof I have made each quantifier in sections to explicitly show the proof.
I model clause satisfaction by companion cubes.
Assuming you can always move companion cubes between rooms if one companion cube is with you then the $or$ operation satisfies and you can pass.
Note that each door is dependent on the next one if they are in a line in portal or if they are in one path.
For the reverse operation on 2.a I allow you to portal backwards and have a piston allow you to go up.
Removal of Portal Restriction
If we allow for unrestricted portals and your portal simplifies the problem occurs then this removes quantifiers and sets the variable to be true.
For 2.a and 2.b if there is the ability to shoot a portal past the door then you skip the quantifier.
For 2.c if you allow successful portaling you skip the whole clause.
What does the physics engine do for computational complexity?