Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [ppad]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
21 votes
2 answers
2k views

Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE: END OF THE LINE: Given circuits S and P ...
Daniel Apon's user avatar
  • 6,001
13 votes
2 answers
620 views

Does PPAD really capture the notion of finding another unbalanced vertex?

Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. The class is designed to capture the complexity of search problems where the existence of a solution is ...
Daniil Musatov's user avatar
15 votes
1 answer
305 views

Does ${\bf AC^0PAD} = {\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? Recently giving ...
domotorp's user avatar
  • 14k
13 votes
1 answer
519 views

Why are these two definitions of PPAD equivalent?

The complexity class PPAD is usually defined by stating that End-Of-The-Line is PPAD-complete. End-Of-The-Line is a search problem. The input consists of a directed graph in which each node has in-...
Matthias's user avatar
  • 1,668
9 votes
1 answer
924 views

When do $\epsilon$-Nash equilibrium strategies converge to Nash Equilibrium strategies?

Nash Equilibria are uncomputable in general. An $\epsilon$-Nash equilibrium is a set of strategies where, given the opponents' strategies, each player obtains within $\epsilon$ of the maximum possible ...
usul's user avatar
  • 7,615