论文标题
使用随机类洞察投票问题复杂性
Insight into Voting Problem Complexity Using Randomized Classes
论文作者
论文摘要
分类NP问题的复杂性的第一步通常是在p或NP组中显示该问题。对于许多问题，包括投票问题，这是成功的第一步。但是，在本文中，我们表明这可能并不总是是最好的第一步。我们通过替换Loreggia等人引入的选民（CCRV）来考虑建设性控制的问题。 （2015）对于得分规则第一持久，该规则由$ \ langle 1，0，\ dots，0，-1 \ rangle $定义。我们表明，这个问题等同于精确的完美双方匹配，因此可以在随机多项式时间内确定第一last的CCRV。因此，一方面，如果用于第一last的CCRV是NP完整的，则RP = NP，这是极不可能的。另一方面，表明第一持久的CCRV在P中也表明，p中精确的完美二分匹配是在P中，这将解决一个经过良好研究的40年历史的开放问题。 通过将RP作为一种选择，我们还可以深入了解CCRV对2批准的复杂性，最终在P中显示了CCRV的复杂性，这在Erdélyi等人的综合表中解决了唯一开放问题的复杂性。 （2021）。
The first step in classifying the complexity of an NP problem is typically showing the problem in P or NP-complete. This has been a successful first step for many problems, including voting problems. However, in this paper we show that this may not always be the best first step. We consider the problem of constructive control by replacing voters (CCRV) introduced by Loreggia et al. (2015) for the scoring rule First-Last, which is defined by $\langle 1, 0, \dots, 0, -1\rangle$. We show that this problem is equivalent to Exact Perfect Bipartite Matching, and so CCRV for First-Last can be determined in random polynomial time. So on the one hand, if CCRV for First-Last is NP-complete then RP = NP, which is extremely unlikely. On the other hand, showing that CCRV for First-Last is in P would also show that Exact Perfect Bipartite Matching is in P, which would solve a well-studied 40-year-old open problem. By considering RP as an option we also gain insight into the complexity of CCRV for 2-Approval, ultimately showing it in P, which settles the complexity of the sole open problem in the comprehensive table from Erdélyi et al. (2021).
