The Classes PPA-$k$: Existence from Arguments Modulo $k$

Abstract

The complexity classes PPA-$k$, $k\ge 2$, have recently emerged as the main candidates for capturing the complexity of important problems in fair division, in particular Alon's Necklace-Splitting problem with $k$ thieves. Indeed, the problem with two thieves has been shown complete for PPA = PPA-2. In this work, we present structural results which provide a solid foundation for the further study of these classes. Namely, we investigate the classes PPA-$k$ in terms of (i) equivalent definitions, (ii) inner structure, (iii) relationship to each other and to other TFNP classes, and (iv) closure under Turing reductions.

Final journal version. Preliminary version appeared at WINE 2019

References in corpus (1)

• On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem

Cited by in corpus (1)

• Consensus-Halving: Does It Ever Get Easier?