The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
Aris Filos-Ratsikas, Paul W. Goldberg · SIAM Journal on Computing · 2022
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.