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
1 vote
0 answers
40 views

Encoding of continuous functions in PPAD

I'm studying the complexity class PPAD (from the seminal 1994 work by Papadimitriou) which contains complete problems such as computing Nash equilibria or finding the fixed point of a Brouwer map. ...
5 votes
1 answer
237 views

How hard is Hex from a symmetric position?

It is known that determining who wins Hex from an arbitrary position is PSPACE-vollständig but of course a strategy stealing argument guarantees that the first player wins on the empty board or, more ...
3 votes
1 answer
95 views

END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node

The END OF THE LINE problem is stated as Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find ...
30 votes
2 answers
893 views

Proof refutation: Amateur reviews of ambitious CoRR papers

I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I ...
5 votes
0 answers
202 views

Generating Where's Waldo?

I want a challenging Where's Waldo type game, where the goal is to find some pattern. But I would want something where you can make your own puzzles, for example by randomly pulling your hand over a ...
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 ...
8 votes
0 answers
103 views

Does ${\bf CFLPAD}={\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem? I asked a similar ...
9 votes
0 answers
251 views

Which version of KAKUTANI does lie in PPAD?

The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite ...
6 votes
1 answer
186 views

Is End-of-Monotone-Line PPAD-complete?

Consider the following problem from TFNP that is somewhere between End-of-the-Line (PPAD) and End-of-Metered-Line (CLS). Input (via polynomial circuit): Graph on vertex set $0$ to $2^n-1$ such that ...
2 votes
1 answer
308 views

What does $\#P\subseteq FP^{PPAD}$ imply?

We know $\#P\subseteq {PPAD}\implies PH\subseteq P^{{PPAD}}\subseteq P^{{NP}}$ and the polynomial hierarchy collapses ($FP^{PPAD}=PPAD$ following Emil Jerabek's comment). Can $\#P\subseteq {PPAD}$ ...
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-...
8 votes
1 answer
285 views

What's the complexity of counting odd nodes in graph?

According to Handshaking Lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are ...
6 votes
1 answer
159 views

Are there PPAD-complete puzzles?

Most puzzles that you can buy are in P, NP-complete (like Sudoku) or PSPACE-complete (like Sokoban), at least if you scale them up. Are there any natural puzzles that are PPAD-complete? What about ...
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 ...
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 ...
22 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 ...