The complexity of necklace splitting, consensus-halving, and discrete ham sandwich - Filos-Ratsikas, A; Goldberg, PW (Society for Industrial and Applied Mathematics, 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.