2
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ I am very confused about the purpose of this question? $\endgroup$ – Sasho Nikolov Jul 8 '12 at 5:30
  • 2
    $\begingroup$ @Sasho: Revision 1 of this question had a clear purpose. It was a reference request, and it is understandable to me that before writing up something, the author wants to check that the result is new. (Whether asking a question on cstheory.stackexchange.com is a good way to check it or not is a separate matter.) Now the purpose is less clear because it primarily asks for techniques, but note that Stack Exchange encourages posting a piece of knowledge in the form of a self-answered question. (Again, whether it is a good way to communicate a research result is a separate matter.) $\endgroup$ – Tsuyoshi Ito Jul 8 '12 at 9:42
  • 6
    $\begingroup$ It might be better if you leave the question for a day, reread your own question after one day, and then decide what to do. $\endgroup$ – Tsuyoshi Ito Jul 8 '12 at 15:20
  • 4
    $\begingroup$ As it is written, this is not a question but an announcement of your personal result. Thus it does not belong on cstheory, but on your blog. I am casting my vote to close as NARQ. $\endgroup$ – Artem Kaznatcheev Jul 10 '12 at 2:21
  • 2
    $\begingroup$ I rewrote the question. It should be fine now. $\endgroup$ – Kaveh Jul 11 '12 at 4:52
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm going to do restricted portal and then actual portal. Restricted portal is without portalable surfaces and actual portal is with portable surfaces $\endgroup$ – Joshua Herman Jul 8 '12 at 0:27
  • 7
    $\begingroup$ See also Erik Demaine and Bob Hearn's monograph Games, Puzzles, and Computation. $\endgroup$ – Jeffε Jul 8 '12 at 1:18
14
+100
$\begingroup$

(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:

http://steamcommunity.com/sharedfiles/filedetails/?id=73499175

$\endgroup$
  • $\begingroup$ This is only using a subset of portal as a computer. I'm using the path information to encode pspace. Pspace contains NP-hard. Thank you for the NP hard proof I will cite it. I am making a combined answer $\endgroup$ – Joshua Herman Jul 8 '12 at 4:41
  • 2
    $\begingroup$ Yes, it does not use everything Portal 2 has to offer. We discussed ways to proved harder hardness, but no conclusions yet. $\endgroup$ – Tyson Williams Jul 8 '12 at 13:48
  • $\begingroup$ @TysonWilliams: Just a word from the moderator. If you think questions are off-topic, please vote to close them rather than always notifying the moderators. Let the community tools do their work! $\endgroup$ – Dave Clarke Oct 12 '12 at 13:19
  • $\begingroup$ @DaveClarke This discussion is off topic here. Let's continue in chat. $\endgroup$ – Tyson Williams Oct 14 '12 at 15:12
1
$\begingroup$

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.

Gaming is a hard job metatheorem 2.a,b,c

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.

Clause Satisfaction

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.

Further work

What does the physics engine do for computational complexity?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.