Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul G. Spirakis · Journal of Computer and System Sciences · 2020
We study the problem of finding an exact solution to the Consensus Halving problem. While recent work has shown that the approximate version of this problem is PPA -complete [29] , [30] , we show that the exact version is much harder. Specifically, finding a solution with n agents and n cuts is FIXP -hard, and deciding whether there exists a solution with fewer than n cuts is ETR -complete. Along the way, we define a new complexity class, called BU , which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP ⊆ BU ⊆ TFETR and that LinearBU = PPA , where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit .