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 establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.

Authors

• Aris Filos-Ratsikas
• Paul W. Goldberg

Keywords

• Consensus-Halving
• Necklace Splitting
• PPA-Completeness