Deligkas, Argyrios, Fearnley, John, Melissourgos, Themistoklis ORCID: 0000-0002-9867-6257 and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2021)
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem.
In: ICALP 2019.
Text
note.pdf - Author Accepted Manuscript Download (719kB) |
Abstract
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.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | PPA, FIXP, ETR, Consensus halving, Circuit, Reduction, Complexity class |
Depositing User: | Symplectic Admin |
Date Deposited: | 29 Apr 2019 07:59 |
Last Modified: | 19 Jan 2023 00:53 |
DOI: | 10.1016/j.jcss.2020.10.006 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3038523 |