Benutzer: Gast  Login
Titel:

Computing exact solutions of consensus halving and the Borsuk-Ulam theorem

Dokumenttyp:
Zeitschriftenaufsatz
Autor(en):
Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G.
Nicht-TUM Koautoren:
ja
Kooperation:
international
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...     »
Stichworte:
PPA, FIXP, ETR, Consensus halving, Circuit, Reduction, Complexity class
Intellectual Contribution:
Contribution to Practice
Zeitschriftentitel:
Journal of Computer and System Sciences
Journal gelistet in FT50 Ranking:
nein
Jahr:
2021
Band / Volume:
117
Seitenangaben Beitrag:
75 - 98
Volltext / DOI:
doi:10.1016/j.jcss.2020.10.006
WWW:
http://www.sciencedirect.com/science/article/pii/S0022000020300994
Print-ISSN:
0022-0000
Urteilsbesprechung:
0
Key publication:
Ja
Peer reviewed:
Ja
commissioned:
not commissioned
Technology:
Nein
Interdisziplinarität:
Nein
Leitbild:
;
Ethics und Sustainability:
Nein
 BibTeX
Versionen