Conference item
The complexity of splitting necklaces and bisecting ham sandwiches
- Abstract:
- We resolve the computational complexity of two problems known as Necklace-splitting and Discrete Ham Sandwich showing that they are PPA-complete. For Necklace-splitting, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the Consensus-halving problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional Möbius strip in the Consensus-halving problem. These results settle the status of PPA as a class that captures the complexity of “natural” problems whose definitions do not incorporate a circuit.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 928.3KB, Terms of use)
-
- Publisher copy:
- 10.1145/3313276.3316334
Authors
- Publisher:
- Association for Computing Machinery
- Journal:
- STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing More from this journal
- Pages:
- 638-649
- Publication date:
- 2019-06-23
- Event title:
- 51st Annual ACM SIGACT Symposium
- Event location:
- Phoenix, Arizona, USA
- Event website:
- https://dl.acm.org/doi/proceedings/10.1145/3313276
- Event start date:
- 2019-06-23
- Event end date:
- 2019-06-26
- DOI:
- ISSN:
-
0737-8017
- ISBN:
- 9781450367059
- Language:
-
English
- Keywords:
- Pubs id:
-
860079
- Local pid:
-
pubs:860079
- Deposit date:
-
2020-01-29
Terms of use
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2019
- Rights statement:
- © 2019 Association for Computing Machinery.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from the Association for Computing Machinery at: https://doi.org/10.1145/3313276.3316334
If you are the owner of this record, you can report an update to it here: Report update to this record