  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, we show that the exact version is much harder.
Specifically, finding a solution with $n$ cuts is FIXP-hard, and deciding
whether there exists a solution with fewer than $n$ cuts is ETR-complete. We
also give a QPTAS for the case where each agent's valuation is a polynomial.
Along the way, we define a new complexity class BU, which captures all problems
that can be reduced to solving an instance of the Borsuk-Ulam problem exactly.
We show that FIXP $\subseteq$ BU $\subseteq$ 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.
