The complexity of necklace splitting, consensus-halving, and discrete ham sandwich
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 th...
| Príomhchruthaitheoirí: | , |
|---|---|
| Formáid: | Journal article |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Society for Industrial and Applied Mathematics
2022
|