# What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD

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.

• Did you try the Complexity Zoo? Mar 15 '11 at 13:22
• 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! Mar 15 '11 at 13:38
• Please update the question so that people do not have to repeat the same comment as Robin’s. Mar 15 '11 at 14:17
• 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. Mar 16 '11 at 7:44
• 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: cstheory.stackexchange.com/questions/1886/… May 10 '11 at 15:12

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.
• 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. Mar 16 '11 at 7:56