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
|