Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: helping

Sortuj według:

Ogranicz wyniki do:

Relativized helping operators

Cintioli P.

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

2005

Vol. 9, No 3

357-367

Schöning and Ko respectively introduced the concepts of helping and one-side-helping, and then defined new operators, Phelp(•) and P1-help(•), acting on classes of sets C and returning classes of sets Phelp(C) and P1-help(C). A number of results have been obtained on this subject, principally devoted to understanding how wide the Phelp(C) and P1-help(C) classes are. For example, it seems that the Phelp(•) operator contracts NP ∩ coNP}, while the P1-help(•) operator enlarges UP. To better understand the relative power of P1-help(•) versus Phelp(•) we propose to search, for every relativizable class D containing P, the largest relativizable class C containing P such that for every oracle B PBhelp(CB)? PB1-help(DB). In the following paper: Cintioli P. and Silvestri R. 1997 Inf. Proc. Let. 61 189, it has been observed that Phelp(UP ∩ coUP)= P1-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 PAhelp(UPA2 ∩ coUPA2) is not contained in PA1-help(UPA ∩ coUPA). We also prove that for every integer k ≥ 2 there exists an oracle A such that PAhelp(UPAk ∩ coUPAk) ? UPAk.