For each of the seven general electoral control type collapses found by Hemaspaandra, Hemaspaandra, and Menton [HHM20] and each of the additional electoral control type collapses of Carleton et al. [CCH+22] for veto and approval (and many other election systems in light of that paper's Theorems 3.6 and 3.9), the collapsing types obviously have the same complexity since as sets they *are* the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [HHM20] and Carleton et al. [CCH+22] we prove that the pair's members' complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. We also, for the concrete systems plurality, veto, and approval completely determine which of those polynomially-related search-problem pairs are polynomial-time computable and which are NP-hard.
翻译:对于Hemaspaandra、Hemaspaandra和Menton[HHM20]所发现的七种大选控制类型的崩溃,以及Carleton等人[CCH+22][CCH+22]为否决和批准(以及根据该文件的Theorems 3.6和3.9,许多其他选举制度)所发现的另外一种选举控制类型的崩溃,这些崩溃类型显然都具有相同的复杂性,因为它们是同一组的。然而,具有同样的复杂性(与组一样)不足以保证与搜索问题同样复杂。在本文中,我们探讨了倒闭配对的搜索版本之间的关系。对于Hemaspaandra、Hmaspaandra、Menton[HHMHM20]和Carleton等人的每对倒闭配对来说,我们证明夫妻成员的复杂性是多式的(如果赢家问题本身不是多式的,那么连锁的,那么赢家问题就是一个或错的问题。此外,我们从一个解决方案到一个彻底的压式的削减,我们决定了这些和多式的系统。