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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2022
|
| _version_ | 1797110800672882688 |
|---|---|
| author | Filos-Ratsikas, A Goldberg, PW |
| author_facet | Filos-Ratsikas, A Goldberg, PW |
| author_sort | Filos-Ratsikas, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T08:01:25Z |
| format | Journal article |
| id | oxford-uuid:00c1d4bb-8630-4130-a710-b841c29cac63 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:01:25Z |
| publishDate | 2022 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:00c1d4bb-8630-4130-a710-b841c29cac632023-10-02T09:57:57ZThe complexity of necklace splitting, consensus-halving, and discrete ham sandwichJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:00c1d4bb-8630-4130-a710-b841c29cac63EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics 2022Filos-Ratsikas, AGoldberg, PWWe 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. |
| spellingShingle | Filos-Ratsikas, A Goldberg, PW The complexity of necklace splitting, consensus-halving, and discrete ham sandwich |
| title | The complexity of necklace splitting, consensus-halving, and discrete ham sandwich |
| title_full | The complexity of necklace splitting, consensus-halving, and discrete ham sandwich |
| title_fullStr | The complexity of necklace splitting, consensus-halving, and discrete ham sandwich |
| title_full_unstemmed | The complexity of necklace splitting, consensus-halving, and discrete ham sandwich |
| title_short | The complexity of necklace splitting, consensus-halving, and discrete ham sandwich |
| title_sort | complexity of necklace splitting consensus halving and discrete ham sandwich |
| work_keys_str_mv | AT filosratsikasa thecomplexityofnecklacesplittingconsensushalvinganddiscretehamsandwich AT goldbergpw thecomplexityofnecklacesplittingconsensushalvinganddiscretehamsandwich AT filosratsikasa complexityofnecklacesplittingconsensushalvinganddiscretehamsandwich AT goldbergpw complexityofnecklacesplittingconsensushalvinganddiscretehamsandwich |