0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Did you try the Complexity Zoo? $\endgroup$
    – Robin Kothari
    Commented Mar 15, 2011 at 13:22
  • $\begingroup$ 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! $\endgroup$
    – Zelah 02
    Commented Mar 15, 2011 at 13:38
  • 3
    $\begingroup$ Please update the question so that people do not have to repeat the same comment as Robin’s. $\endgroup$
    – Tsuyoshi Ito
    Commented Mar 15, 2011 at 14:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Mar 16, 2011 at 7:44
  • $\begingroup$ 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/… $\endgroup$
    – Artem Kaznatcheev ♦
    Commented May 10, 2011 at 15:12

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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 (specifically Figure 1)

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Mar 16, 2011 at 7:56
  • $\begingroup$ This is a nice set of slides expanding on the above answer. $\endgroup$
    – Artem Kaznatcheev ♦
    Commented Jan 5, 2017 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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