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.

$\endgroup$
5
  • 4
    $\begingroup$ Did you try the Complexity Zoo? $\endgroup$ Mar 15 '11 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
    Mar 15 '11 at 13:38
  • 3
    $\begingroup$ Please update the question so that people do not have to repeat the same comment as Robin’s. $\endgroup$ Mar 15 '11 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
    Mar 16 '11 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$ May 10 '11 at 15:12
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.

$\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)

$\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
    Mar 16 '11 at 7:56
  • $\begingroup$ This is a nice set of slides expanding on the above answer. $\endgroup$ Jan 5 '17 at 20:12

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.