Skip to main content
Theoretical Computer Science

Return to Question

Tweeted twitter.com/#!/StackCSTheory/status/48843681159065600
edited tags
Link
Suresh Venkat
Suresh Venkat
  • 32.2k
  • 4
  • 97
  • 272
edited title
Link
Zelah 02
Zelah 02
  • 1.6k
  • 7
  • 16

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

Source Link
Zelah 02
Zelah 02
  • 1.6k
  • 7
  • 16

What is 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.

Thanks in advance.