Search versus Decision for Election Manipulation Problems

作     者：Hemaspaandra, Edith Hemaspaandra, Lane A. Menton, Curtis 

作者机构：Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Univ Rochester Dept Comp Sci Rochester NY 14627 USA Google Inc Mountain View CA 94043 USA 

出 版 物：《ACM TRANSACTIONS ON COMPUTATION THEORY》 (美国计算机学会计算理论汇刊)

年 卷 期：2020年第12卷第1期

页      面：3-3页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Alexander von Humboldt Foundation NSF [CCF-0915792, CCF-1101452] 

主　　题：Structural complexity theory search versus decision borodin-demers theorem NP intersect coNP elections typical-case complexity 

摘      要：Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated rather than the search problem of finding the, successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If P not equal NP boolean AND coNP (Which itself is well known to hold if integer factoring is hard), then for election manipulation, election bribery, and sonic types of election control, there are election systems for which the problem of recognizing which instances can be successfully manipulated is polynomial-time solvable, yet the task of producing the successful manipulations cannot be done in polynomial time.