RELATIVIZED HELPING OPERATORS

Abstract

Sch¨oning and Ko respectively introduced the concepts of helping and one-side-helping, and then defined new operators, P_help(·) and P_1−help(·), acting on classes of sets C and returning classes of sets P_help(C) and P_1−help(C). A number of results have been obtained on this subject, principally devoted to understanding how wide the P_help(C) and P_1−help(C) classes are. For example, it seems that the P_help(·) operator contracts NP∩coNP, while the P_1−help(·) operator enlarges UP. To better understand the relative power of P_1−help(·) versus P_help(·) we propose to search, for every relativizable class D containing P, the largest relativizable class C containing P such that for every oracle B P^B_help(C^B) ⊆ P^B_1−help(D^B). In [1] it has been observed that P_help(UP∩coUP) = P_1−help(UP∩coUP), and this is true in any relativized world. In this paper we consider the case of D = UP∩coUP and demonstrate the existence of an oracle A for which P^A_help(UP₂^A ∩coUP₂^A) is not contained in P^A_1−help(UP^A ∩coUP^A). We also prove that for every integer k ≥ 2 there exists an oracle A such that P^A_help(UP_k^A ∩coUP_k^A) 6⊆ UP_k^A.