Revisiting a result of Ko

作     者：Cintioli, P Silvestri, R 

作者机构：UNIV ROMA LA SAPIENZADIPARTIMENTO SCI INFORMAZI-00198 ROMEITALY UNIV CAMERINODIPARTIMENTO MATEMAT & FISI-62032 CAMERINOMCITALY 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1997年第61卷第4期

页      面：189-194页

核心收录：

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

主　　题：theory of computation computational complexity relativizations robust algorithms 

摘      要：In this paper we analyze Ko s Theorem 3.4 in [9]. We extend point (b) of Ko s Theorem by showing that P1-help (UP boolean AND co-UP) = UP boolean AND co-UP. As a corollary, we get the equality P-help (UP boolean AND co-UP)= P1-help (UP boolean AND co-UP), which is, to our knowledge, a unique result of type P1-help (C) = P-help (C), for a class C that would not be equal to P. With regard to point (a) of Ko s Theorem, we observe that it also holds for the classes UP( )k and for FewP. In spite of this, we prove that point (b) of Theorem 3.4 fails for such classes in a relativized world. This is obtained by showing the relativized separation of UP2 boolean AND co-UP2 from P1-help (NP boolean AND co-NP). Finally, we suggest a natural line of research arising from these facts.