<p>PPAD and PLS are subclasses of TFNP, which in turn is a subclass of FNP. While I'm not entirely certain about this next claim, it seems that FNP should be trivially in PSPACE, since the class is defined in terms of binary predicates $P(x,y)$ such that the truth of $P(x,y)$ for a given x and poly-bounded y can be determined in polytime.</p>

<p>In addition, PPAD is a subclass of both PPA and PPP. for more on this, see the <a href="http://www.siam.org/proceedings/soda/2011/SODA11_061_daskalakisc.pdf" rel="nofollow">recent Papadimitriou/Daskalakis paper on continuous local search</a> (specifically Figure 1)</p>

CC BY-SA 2.5
2011-03-16T07:56:51.747Z
There might be a small technical problem with $\mathbb{FNP}$ being a class of multi-functions not functions, but if we define when a multifunction is computed by a $\mathbb{FPSpace}$ machine then everything seems to work.
Kaveh
CC BY-SA 3.0
2017-01-05T20:12:48.847Z
[This is a nice set of slides](http://www.math.ucsd.edu/~sbuss/ResearchWeb/Cambridge2012/npsearchTalk.pdf) expanding on the above answer.
Artem Kaznatcheev
CC BY-SA 2.5
2011-03-16T06:12:30.353Z
2011-03-16T06:37:06.730Z
2011-03-16T06:37:06.730Z
Suresh Venkat
<p>Strictly speaking, PSPACE contains decision problems, while the others are search problems, so they live in different zoos, but FPSPACE would of course contain all the other problems. Then PPAD is contained in both PPA and PPP, whose relationship is unknown, but were separated by an oracle in Beame et al: Relative complexity of NP search problems. Here the PLS class was not considered, that was separated by an oracle later in Morioka: Relative complexity of local search heuristics and the iteration principle from all the other three classes. (For me this latter paper was too hard to read.) Without oracles, nothing is known.</p>

CC BY-SA 2.5
2011-03-16T06:56:40.867Z
2011-03-16T06:56:40.867Z
domotorp
<p>I have been thinking about Pspace in conjunction with searching for a Natural Notion of Stablilty for Complex Dynamical Systems.</p>

<p>A natural question in this direction is the Nash equilibrium. Surprizingly, it appears that Games in Normal Form have Nash equilibria which is PPAD complete. This has led myself to wonder about the inclusion relationships of various associated Complexity Classes. </p>

<p>Thanks in advance.</p>

CC BY-SA 2.5
2011-03-15T13:22:57.473Z
Did you try the [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo)?
Robin Kothari
CC BY-SA 2.5
2011-03-15T13:38:46.087Z
The Complexity Zoo does some of the work, but the main ingredient is the relationship of PLS to PPP,PPA and PPAD! Sorry for the confusion here!
Zelah 02
CC BY-SA 2.5
2011-03-15T14:17:37.817Z
Please update the question so that people do not have to repeat the same comment as Robin’s.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-16T07:44:54.160Z
If the complexity class is in the Complexity Zoo but the relation is not, then it means that with considerable probability the relation is unknown/open.
Kaveh
CC BY-SA 3.0
2011-05-10T15:12:12.593Z
Would you care to elaborate on the relationship between PSPACE and stability in dynamic systems? If you are just looking at various equilibria conditions and their complexity, the following question might be of interest: http://cstheory.stackexchange.com/questions/1886/algorithmic-game-theory-nonstandard-equilibrium-concepts
Artem Kaznatcheev
<cc.complexity-theory><gt.game-theory>
What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD
Zelah 02
# What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD

(Asked by: username_0 on 2011-03-15)

I have been thinking about Pspace in conjunction with searching for a Natural Notion of Stablilty for Complex Dynamical Systems.

A natural question in this direction is the Nash equilibrium. Surprizingly, it appears that Games in Normal Form have Nash equilibria which is PPAD complete. This has led myself to wonder about the inclusion relationships of various associated Complexity Classes.

Thanks in advance.

**Tags:** cc.complexity-theory, gt.game-theory
> **Comments:**
> **username_1**: Did you try the [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo)?  
> **username_0**: The Complexity Zoo does some of the work, but the main ingredient is the relationship of PLS to PPP,PPA and PPAD! Sorry for the confusion here!  
> **username_2**: Please update the question so that people do not have to repeat the same comment as Robin’s.  
> **username_3**: If the complexity class is in the Complexity Zoo but the relation is not, then it means that with considerable probability the relation is unknown/open.  
> **username_4**: Would you care to elaborate on the relationship between PSPACE and stability in dynamic systems? If you are just looking at various equilibria conditions and their complexity, the following question might be of interest: http://cstheory.stackexchange.com/questions/1886/algorithmic-game-theory-nonstandard-equilibrium-concepts  

---

## 2 answers

### Answer by username_6 on 2011-03-16. Score: 9 | Accepted answer

Strictly speaking, PSPACE contains decision problems, while the others are search problems, so they live in different zoos, but FPSPACE would of course contain all the other problems. Then PPAD is contained in both PPA and PPP, whose relationship is unknown, but were separated by an oracle in Beame et al: Relative complexity of NP search problems. Here the PLS class was not considered, that was separated by an oracle later in Morioka: Relative complexity of local search heuristics and the iteration principle from all the other three classes. (For me this latter paper was too hard to read.) Without oracles, nothing is known.


---

### Answer by username_5 on 2011-03-16. Score: 4

PPAD and PLS are subclasses of TFNP, which in turn is a subclass of FNP. While I'm not entirely certain about this next claim, it seems that FNP should be trivially in PSPACE, since the class is defined in terms of binary predicates $P(x,y)$ such that the truth of $P(x,y)$ for a given x and poly-bounded y can be determined in polytime.

In addition, PPAD is a subclass of both PPA and PPP. for more on this, see the [recent Papadimitriou/Daskalakis paper on continuous local search](http://www.siam.org/proceedings/soda/2011/SODA11_061_daskalakisc.pdf) (specifically Figure 1)

> **Comments:**
> **username_3**: There might be a small technical problem with $\mathbb{FNP}$ being a class of multi-functions not functions, but if we define when a multifunction is computed by a $\mathbb{FPSpace}$ machine then everything seems to work.  
> **username_4**: [This is a nice set of slides](http://www.math.ucsd.edu/~sbuss/ResearchWeb/Cambridge2012/npsearchTalk.pdf) expanding on the above answer.  

---

