Abstrakt. Vi studerar problemet med att hitta en exakt lösning på problemet med halvering av samförståndet. Även om det senaste arbetet har visat att den ungefärliga versionen av detta problem är PPA-komplett [28,27], visar vi att den exakta versionen är mycket svårare. Särskilt, hitta en lösning med n skärningar är FIXPhard, och avgöra om det finns en lösning med färre än n skärningar är ETR-fullständig. Vi ger också en QPTAS för fallet där varje agent värdering är ett polynom. Längs vägen definierar vi en ny komplexitetsklass BU, som fångar alla problem som kan reduceras till att lösa ett fall av Borsuk-Ulam-problemet exakt. Vi visar att FIXP  och BU TFETR och att LinearBU = PPA, där LinearBU är den underklass av BU där Borsuk-Ulam instansen specificeras av en linjär aritmetisk krets.
Nyligen, REF studerade komplexiteten i exakt Consensus-Halving och visade att problemet är FIXP-hård.
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}