Skip to main content

Questions tagged [ppad]

The tag has no usage guidance.

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
253 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 ...
Daniil Musatov's user avatar
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 ...
domotorp's user avatar
  • 14k
5 votes
0 answers
203 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 ...
domotorp's user avatar
  • 14k
1 vote
0 answers
41 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. ...
ntrstd11's user avatar
  • 111