Back to Search
Start Over
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- Source :
- SIAM Journal on Computing. 52:STOC19-200
- Publication Year :
- 2022
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 2022.
-
Abstract
- We resolve the computational complexity of three problems known as Necklace Splitting, Consensus-Halving, 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. These are the first PPA-completeness results for problems whose definition does not contain an explicit circuit, thus settling the status of PPA as a class that captures the complexity of such “natural' problems.
- Subjects :
- General Computer Science
General Mathematics
Subjects
Details
- ISSN :
- 10957111 and 00975397
- Volume :
- 52
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Computing
- Accession number :
- edsair.doi.dedup.....b6428547b8d781ae2f7969719c82d40a