Share Your Experience: Take the 2024 Developer Survey

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
1 vote
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
186 views

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 ...
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}$ ...
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-...
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 ...
159 views

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 ...
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 ...
### 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 ...