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\'{e}lyi et al. (2021).

翻译：对NP问题的复杂性进行分类的第一步通常显示P或NP问题完成后的问题。 这是包括投票问题在内的许多问题的成功的第一步。 但是, 在本文中, 我们显示这并不总是最佳的第一步。 我们考虑建设性控制的问题, 替换Loreggia等人(CCRV)为成绩第一至最后规则提出的选民( CCCRV ), 排名第一至最后规则由$langle 1, 0,\ dots, 0, -1\rangle$定义。 我们显示, 这个问题相当于完成完美双部分配对, 因而第一至最后几个问题的CCCRV 可以在随机的多元时间里决定。 因此, 一方面, 如果CCRRV 完成, 然后RP = NP, 这是极不可能的。 另一方面, 显示第一至最后的 CCRV 也显示 Exact Perpartite 匹配在 P 和 P 中, 将解决一个经过良好研究的40年期的CRV 复杂程度, 最终将显示一个选项, 进入第 2 ALRP 。