Consensus Halving is PPA-Complete
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 13 Nov 2017.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 1.
1 paper.