BANISHING ROBUST TURING COMPLETENESS

作     者：LANE A. HEMASPAANDRA SANJAY JAIN NIKOLAI K. VERESHCHAGIN 

作者机构：Department of Computer Science University of Rochester Rochester New York 14627 USA Supported in part by a Hewlett-Packard Corporation equipment grant and by the National Science Foundation under grants CCR-8809174/CCR-8996198 CCR-8957604 and NSF-INT-9116781/JSPS-ENG-207. Institute of Systems Science National University of Singapore Singapore 0511 Republic of Singapore The Institute of New Technologies Kirovogradskaja 11 Moscow 113587 Russia 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1993年第4卷第3期

页      面：245-265页

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

主　　题：Structural complexity theory Polynomial-time reductions Complete languages 

摘      要：This paper proves that “promise classes are so fragilely structured that they do not robustly (i.e. with respect to all oracles) possess Turinghard sets even in classes far larger than themselves. In particular, this paper shows that FewP does not robustly possess Turing hard sets for UP∩coUP and IP∩coIP does not robustly possess Turing hard sets for ZPP. It follows that ZPP, R, coR, UP∩coUP, UP, FewP∩coFewP, FewP, and IP∩coIP do not robustly possess Turing complete sets. This both resolves open questions of whether promise classes lacking robust downward closure under Turing reductions (e.g., R, UP, FewP) might robustly have Turing complete sets, and extends the range of classes known not to robustly contain many-one complete sets.