Consensus halving is PPA-complete
We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establi...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Association for Computing Machinery
2018
|
| _version_ | 1797066185592799232 |
|---|---|
| author | Filos-Ratsikas, A Goldberg, P |
| author_facet | Filos-Ratsikas, A Goldberg, P |
| author_sort | Filos-Ratsikas, A |
| collection | OXFORD |
| description | We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete. |
| first_indexed | 2024-03-06T21:38:48Z |
| format | Conference item |
| id | oxford-uuid:472f969d-3bbb-46a9-83db-38dd60218004 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:38:48Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:472f969d-3bbb-46a9-83db-38dd602180042022-03-26T15:18:32ZConsensus halving is PPA-completeConference itemhttp://purl.org/coar/resource_type/c_5794uuid:472f969d-3bbb-46a9-83db-38dd60218004Symplectic Elements at OxfordAssociation for Computing Machinery2018Filos-Ratsikas, AGoldberg, PWe show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete. |
| spellingShingle | Filos-Ratsikas, A Goldberg, P Consensus halving is PPA-complete |
| title | Consensus halving is PPA-complete |
| title_full | Consensus halving is PPA-complete |
| title_fullStr | Consensus halving is PPA-complete |
| title_full_unstemmed | Consensus halving is PPA-complete |
| title_short | Consensus halving is PPA-complete |
| title_sort | consensus halving is ppa complete |
| work_keys_str_mv | AT filosratsikasa consensushalvingisppacomplete AT goldbergp consensushalvingisppacomplete |