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 in a cubic graph, which is known to be in PPA, just now known to be complete.


1 Answer 1


In the most authoritative reference on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.