<p>In the <a href="http://www.cs.princeton.edu/~kintali/ppad.html" rel="nofollow">most authoritative reference</a> on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.</p>

CC BY-SA 4.0
2023-03-24T16:20:22.767Z
The most recent archived version of the page: https://web.archive.org/web/20160816142056/http://www.cs.princeton.edu/~kintali/ppad.html
Kevin Wang
CC BY-SA 3.0
2015-01-31T18:29:08.513Z
2015-01-31T18:29:08.513Z
Kapoios
<p>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 <em>natural</em> puzzles that are PPAD-complete?
What about other similar classes, like PPA, PPADS etc?</p>

<p>If we don't insist on natural, then of course practically any PPAD-complete problem would be a puzzle, just during the puzzle you would need to run the some Turing machine a couple of times.
What I have in mind would be for example finding <a href="https://kintali.wordpress.com/2009/07/25/finding-a-second-hamilton-circuit/">another Hamiltonian cycle</a> in a cubic graph, which is known to be in PPA, just now known to be complete.</p>

<puzzles><board-games><ppad>
Are there PPAD-complete puzzles?
domotorp
# Are there PPAD-complete puzzles?

(Asked by: username_0 on 2015-01-31)

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 other similar classes, like PPA, PPADS etc?

If we don't insist on natural, then of course practically any PPAD-complete problem would be a puzzle, just during the puzzle you would need to run the some Turing machine a couple of times.
What I have in mind would be for example finding [another Hamiltonian cycle](https://kintali.wordpress.com/2009/07/25/finding-a-second-hamilton-circuit/) in a cubic graph, which is known to be in PPA, just now known to be complete.

**Tags:** puzzles, board-games, ppad

---

## 1 answers

### Answer by username_1 on 2015-01-31. Score: 2

In the [most authoritative reference](http://www.cs.princeton.edu/~kintali/ppad.html) on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.

> **Comments:**
> **username_2**: The most recent archived version of the page: https://web.archive.org/web/20160816142056/http://www.cs.princeton.edu/~kintali/ppad.html  

---

