- Tytuł:
- Relativized helping operators
- Autorzy:
- Cintioli, P.
- Powiązania:
- https://bibliotekanauki.pl/articles/1964198.pdf
- Data publikacji:
- 2005
- Wydawca:
- Politechnika Gdańska
- Tematy:
-
oracle Turing machines
structural complexity
relativizes separations
helping - Opis:
- 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.
- Źródło:
-
TASK Quarterly. Scientific Bulletin of Academic Computer Centre in Gdansk; 2005, 9, 3; 357-367
1428-6394 - Pojawia się w:
- TASK Quarterly. Scientific Bulletin of Academic Computer Centre in Gdansk
- Dostawca treści:
- Biblioteka Nauki
Artykuł