<p>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.</p>

<p>Some good tools for this are in this paper:</p>

<p>Viglietta, G.  Gaming is a hard job, but someone has to do it! <em>Fun with Algorithms</em> 2012
<a href="http://arxiv.org/pdf/1201.4995v3.pdf">http://arxiv.org/pdf/1201.4995v3.pdf</a></p>

<p>Of course, none of this uses the actual portal aspect of the game.</p>

CC BY-SA 3.0
2012-07-08T00:27:46.603Z
I'm going to do restricted portal and then actual portal. Restricted portal is without portalable surfaces and actual portal is with portable surfaces
Joshua Herman
CC BY-SA 3.0
2012-07-08T01:18:39.640Z
See also Erik Demaine and Bob Hearn's monograph [_Games, Puzzles, and Computation_](http://erikdemaine.org/papers/GPC/).
Jeffε
CC BY-SA 3.0
2012-07-07T23:46:11.663Z
2012-07-07T23:46:11.663Z
SamM
<p>(An earlier version of this question asked if anyone has shown Portal 2 to be NP-hard.)</p>

<p>Yes, someone has done this.  Portal 2 is at least NP-hard.</p>

<p>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:</p>

<p><a href="http://steamcommunity.com/sharedfiles/filedetails/?id=73499175">http://steamcommunity.com/sharedfiles/filedetails/?id=73499175</a></p>

CC BY-SA 3.0
2012-07-08T04:41:41.693Z
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
Joshua Herman
CC BY-SA 3.0
2012-07-08T13:48:29.620Z
Yes, it does not use everything Portal 2 has to offer. We discussed ways to proved harder hardness, but no conclusions yet.
Tyson Williams
CC BY-SA 3.0
2012-10-12T13:19:46.360Z
@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!
Dave Clarke
CC BY-SA 3.0
2012-10-14T15:12:42.337Z
@DaveClarke This discussion is off topic here. Let's continue in chat.
Tyson Williams
CC BY-SA 3.0
2012-07-08T02:58:00.443Z
2012-07-09T14:45:40.160Z
2012-07-09T14:45:40.160Z
Tyson Williams
<p><strong>PSPACE proof attempt of Portal 2 by reduction from TQBF</strong></p>
<p>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?</p>
<p>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.</p>
<p><img src="https://i.sstatic.net/YunKK.png" alt="Gaming is a hard job metatheorem 2.a,b,c" /></p>
<ul>
<li><p>(2.a) <a href="http://steamcommunity.com/sharedfiles/filedetails/?id=80765883" rel="nofollow noreferrer">http://steamcommunity.com/sharedfiles/filedetails/?id=80765883</a></p>
</li>
<li><p>(2.b) <a href="http://steamcommunity.com/sharedfiles/filedetails/?id=80767793" rel="nofollow noreferrer">http://steamcommunity.com/sharedfiles/filedetails/?id=80767793</a></p>
</li>
<li><p>(2.c) <a href="http://steamcommunity.com/sharedfiles/filedetails/?id=80764848" rel="nofollow noreferrer">http://steamcommunity.com/sharedfiles/filedetails/?id=80764848</a></p>
</li>
</ul>
<p><strong>Description of each gadget</strong></p>
<p>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.</p>
<ul>
<li><span class="math-container">$\forall$</span> there is two doors activated by independent switches</li>
<li><span class="math-container">$\exists$</span> is modeled by a sequence of switches with blocks that are deployed and you must put a block for each one.</li>
<li>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.</li>
</ul>
<p><strong>Clause Satisfaction</strong></p>
<p>I model clause satisfaction by companion cubes.</p>
<p>Assuming you can always move companion cubes between rooms if one companion cube is with you then the <span class="math-container">$or$</span> operation satisfies and you can pass.</p>
<p>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.</p>
<p>For the reverse operation on 2.a I allow you to portal backwards and have a piston allow you to go up.</p>
<p><strong>Removal of Portal Restriction</strong></p>
<p>If we allow for unrestricted portals and your portal simplifies the problem occurs then this removes quantifiers and sets the variable to be true.</p>
<p>For 2.a and 2.b if there is the ability to shoot a portal past the door then you skip the quantifier.</p>
<p>For 2.c if you allow successful portaling you skip the whole clause.</p>
<p><strong>Further work</strong></p>
<p>What does the physics engine do for computational complexity?</p>

CC BY-SA 3.0
2012-07-08T04:53:10.043Z
2012-07-08T07:14:03.203Z
2020-06-17T09:38:08.363Z
Joshua Herman
<p>I am studying the complexity of <a href="http://en.wikipedia.org/wiki/Portal_2" rel="nofollow">Portal 2</a> 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.</p>

CC BY-SA 3.0
2012-07-08T05:30:36.587Z
I am very confused about the purpose of this question?
Sasho Nikolov
CC BY-SA 3.0
2012-07-08T05:55:07.220Z
@SashoNikolov Did that explain your question?
Joshua Herman
CC BY-SA 3.0
2012-07-08T07:37:49.317Z
I am afraid it doesn't, actually I am even more confused right now. In general the purpose of a question is to ask something. It seems you announced a problem and (in the original version of the question) you wrote that you'll post your solution in a couple of hours, which you then did. What are you asking for?
Sasho Nikolov
CC BY-SA 3.0
2012-07-08T09:42:39.103Z
@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.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-08T13:08:09.173Z
@TsuyoshiIto Yes, the primary purpose of the question is a ref request. I think I will make a blog post on my blog to answer this question.
Joshua Herman
CC BY-SA 3.0
2012-07-08T14:41:14.180Z
In case it is unclear, no one would think that the primary purpose of the question in its current form (revision 6) is reference request.  If reference request is still your primary purpose of asking this question, you edited the question in a wrong way.
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-08T15:02:37.057Z
@TsuyoshiIto Should I just break it up into two questions?
Joshua Herman
CC BY-SA 3.0
2012-07-08T15:20:51.307Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-09T11:43:54.513Z
I have done this by reduction of the Super Mario brothers paper. 

See http://arxiv.org/abs/1203.1895v1

I will try to answer this question within a few hours with a link to my work.
Joshua Herman
CC BY-SA 3.0
2012-07-10T02:21:34.640Z
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.
Artem Kaznatcheev
CC BY-SA 3.0
2012-07-11T03:17:26.703Z
@ArtemKaznatcheev Okay, I also voted to close. I don't have a blog that I use and it was mainly a reference request. If you want to improve it go ahead. I'm mainly using this as a discussion before I submit to somewhere. I don't have any more time to edit this question so I have submitted it to moderation and we can see what I will do. I believe it would be best to simply delete the post.
Joshua Herman
CC BY-SA 3.0
2012-07-11T04:52:58.230Z
I rewrote the question. It should be fine now.
Kaveh
CC BY-SA 3.0
2012-07-11T05:01:35.743Z
@Kaveh As long as artem and tsuyoshiito agree I will give you the bounty. Thank you very much Kaveh!
Joshua Herman
CC BY-SA 3.0
2012-07-11T05:16:46.323Z
I am in no position to tell you whom you should award the bounty to. It is your bounty, so please award it to anyone you see fit. (But if I am not mistaken, you can award the bounty only to an answerer, not to an editor.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-11T06:49:08.113Z
@JoshuaHerman: Viglietta's "Gaming is a hard job..." and Demaine & Hearn's papers on NCL offer two good starting frameworks for proving the complexity of games; this is another paper about 2D platforms (that can be generalized to 3D): "[Computational complexity of two-dimensional platform games](http://dl.acm.org/citation.cfm?id=1875638)". P.S. I gave a quick read to your proof, perhaps you should explain the elements of the game and how and where they are used in the gadgets (for those like me who doesn't know anything about the game).
Marzio De Biasi
CC BY-SA 3.0
2012-07-11T07:01:05.947Z
@Joshua, editing does need a bounty, the bounty is for answers. :)
Kaveh
CC BY-SA 3.0
2012-07-11T11:58:24.250Z
@Kaveh Fine, I will award you this bounty. If more people complain I will add another bounty. Can you add a answer so I can award it? Or how do I award the bounty if you never write an answer.
Joshua Herman
CC BY-SA 3.0
2012-07-11T16:25:35.080Z
Isn't portal clearly in NP since any level would have a "solution" (a set of key strokes that gets you to the end) that would serve as a certificate? What am I missing?
Lev Reyzin
CC BY-SA 3.0
2012-07-12T07:57:57.923Z
@LevReyzin: but the number of keystrokes can be probably made $O(k^n)$ (I don't know all the elements of the game ... but I suspect that it is PSPACE complete)
Marzio De Biasi
CC BY-SA 3.0
2012-07-12T15:39:38.877Z
Thanks, that makes sense @MarzioDeBiasi.  That's what I had guessed after posting the comment.
Lev Reyzin
CC BY-SA 3.0
2012-07-12T15:45:49.073Z
@Lev Reyzin I can go to #P by looping one room and using Tyson Williams proof. Since #P is the set of function problems I can just write a set of rooms to solve an arbitrary problem in #P. I let the room be the variable that I vary which will solve an NP problem. I dispense a set of companion cubes to be counters. So lets say my function is the set of functions of 8 bits for simplicity. I give you 8 companion cubes to solve the #P problem and encode the NP problem with Tyson Williams proof. Then I start counting down from 8 with the same chamber and I make it solve that problem.
Joshua Herman
CC BY-SA 3.0
2012-07-12T15:58:09.533Z
I see. Don't take this the wrong way, but why are you interested in solving this problem in particular?  It seems Portal 2 is a random modern computer game (not a classic like chess or even tetris) with complicated rules, etc.
Lev Reyzin
CC BY-SA 3.0
2012-07-12T16:04:22.037Z
@LevReyzin I'm so BORED :)
Joshua Herman
<cc.complexity-theory><reference-request><np-hardness><pspace>
Complexity of Portal 2
Joshua Herman
# Complexity of Portal 2

(Asked by: username_0 on 2012-07-07)

I am studying the complexity of [Portal 2](http://en.wikipedia.org/wiki/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.

**Tags:** cc.complexity-theory, reference-request, np-hardness, pspace

> **Comments:**
> **username_1**: I am very confused about the purpose of this question?  
> **username_0**: @SashoNikolov Did that explain your question?  
> **username_1**: I am afraid it doesn't, actually I am even more confused right now. In general the purpose of a question is to ask something. It seems you announced a problem and (in the original version of the question) you wrote that you'll post your solution in a couple of hours, which you then did. What are you asking for?  
> **username_2**: @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.)  
> **username_0**: @TsuyoshiIto Yes, the primary purpose of the question is a ref request. I think I will make a blog post on my blog to answer this question.  
> **username_2**: In case it is unclear, no one would think that the primary purpose of the question in its current form (revision 6) is reference request.  If reference request is still your primary purpose of asking this question, you edited the question in a wrong way.  
> **username_0**: @TsuyoshiIto Should I just break it up into two questions?  
> **username_2**: 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.  
> **username_0**: I have done this by reduction of the Super Mario brothers paper.   See http://arxiv.org/abs/1203.1895v1  I will try to answer this question within a few hours with a link to my work.  
> **username_3**: 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.  
> **username_0**: @ArtemKaznatcheev Okay, I also voted to close. I don't have a blog that I use and it was mainly a reference request. If you want to improve it go ahead. I'm mainly using this as a discussion before I submit to somewhere. I don't have any more time to edit this question so I have submitted it to moderation and we can see what I will do. I believe it would be best to simply delete the post.  
> **username_4**: I rewrote the question. It should be fine now.  
> **username_0**: @username_4 As long as artem and tsuyoshiito agree I will give you the bounty. Thank you very much username_4!  
> **username_2**: I am in no position to tell you whom you should award the bounty to. It is your bounty, so please award it to anyone you see fit. (But if I am not mistaken, you can award the bounty only to an answerer, not to an editor.)  
> **username_5**: @JoshuaHerman: Viglietta's "Gaming is a hard job..." and Demaine & Hearn's papers on NCL offer two good starting frameworks for proving the complexity of games; this is another paper about 2D platforms (that can be generalized to 3D): "[Computational complexity of two-dimensional platform games](http://dl.acm.org/citation.cfm?id=1875638)". P.S. I gave a quick read to your proof, perhaps you should explain the elements of the game and how and where they are used in the gadgets (for those like me who doesn't know anything about the game).  
> **username_4**: @Joshua, editing does need a bounty, the bounty is for answers. :)  
> **username_0**: @username_4 Fine, I will award you this bounty. If more people complain I will add another bounty. Can you add a answer so I can award it? Or how do I award the bounty if you never write an answer.  
> **username_6**: Isn't portal clearly in NP since any level would have a "solution" (a set of key strokes that gets you to the end) that would serve as a certificate? What am I missing?  
> **username_5**: @LevReyzin: but the number of keystrokes can be probably made $O(k^n)$ (I don't know all the elements of the game ... but I suspect that it is PSPACE complete)  
> **username_6**: Thanks, that makes sense @MarzioDeBiasi.  That's what I had guessed after posting the comment.  
> **username_0**: @username_6 I can go to #P by looping one room and using username_9 proof. Since #P is the set of function problems I can just write a set of rooms to solve an arbitrary problem in #P. I let the room be the variable that I vary which will solve an NP problem. I dispense a set of companion cubes to be counters. So lets say my function is the set of functions of 8 bits for simplicity. I give you 8 companion cubes to solve the #P problem and encode the NP problem with username_9 proof. Then I start counting down from 8 with the same chamber and I make it solve that problem.  
> **username_6**: I see. Don't take this the wrong way, but why are you interested in solving this problem in particular?  It seems Portal 2 is a random modern computer game (not a classic like chess or even tetris) with complicated rules, etc.  
> **username_0**: @LevReyzin I'm so BORED :)  

---

## 3 answers

### Answer by username_7 on 2012-07-07. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_0**: I'm going to do restricted portal and then actual portal. Restricted portal is without portalable surfaces and actual portal is with portable surfaces  
> **username_8**: See also Erik Demaine and Bob Hearn's monograph [_Games, Puzzles, and Computation_](http://erikdemaine.org/papers/GPC/).  

---

### Answer by username_9 on 2012-07-08. Score: 14

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

> **Comments:**
> **username_0**: 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  
> **username_9**: Yes, it does not use everything Portal 2 has to offer. We discussed ways to proved harder hardness, but no conclusions yet.  
> **username_10**: @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!  
> **username_9**: @DaveClarke This discussion is off topic here. Let's continue in chat.  

---

### Answer by username_0 on 2012-07-08. Score: 1

**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](https://i.sstatic.net/YunKK.png)

* (2.a) <http://steamcommunity.com/sharedfiles/filedetails/?id=80765883>
* (2.b) <http://steamcommunity.com/sharedfiles/filedetails/?id=80767793>
* (2.c) <http://steamcommunity.com/sharedfiles/filedetails/?id=80764848>

**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?


---

