Journal article
The classes PPA-k: Existence from arguments modulo k
- Abstract:
- The complexity classes PPA-k, k≥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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 434.3KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.tcs.2021.06.016
Authors
- Publisher:
- Elsevier
- Journal:
- Theoretical Computer Science More from this journal
- Volume:
- 885
- Pages:
- 15-29
- Publication date:
- 2021-06-17
- Acceptance date:
- 2021-06-13
- DOI:
- EISSN:
-
1879-2294
- ISSN:
-
0304-3975
- Language:
-
English
- Keywords:
- Pubs id:
-
1217982
- Local pid:
-
pubs:1217982
- Deposit date:
-
2022-03-21
Terms of use
- Copyright holder:
- Elsevier B.V.
- Copyright date:
- 2021
- Rights statement:
- © 2021 Elsevier B.V. All rights reserved.
- Notes:
-
This is the accepted manuscript version of the article. The final version is available from Elsevier at https://doi.org/10.1016/j.tcs.2021.06.016
If you are the owner of this record, you can report an update to it here: Report update to this record