Relativized helping operators

• Autorzy: Cintioli P.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

oracle Turing machines; structural complexity; relativizes separations; helping

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2005
• Tom: Vol. 9, No 3
• Strony: 357--367
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Cintioli P.

• Dipartimento di Matematica e Informatica, Universita di Camerino, Via Madonna delle Carceri, 62032 Camerino, Italy,

Bibliografia

• [1] Cintioli P and Silvestri R 1997 Inf. Proc. Let. 61 189
• [2] Sch¨oning U 1985 Theor. Comp. Sci. 40 57
• [3] Ko K 1987 Theor. Comp. Sci. 52 15
• [4] Cai J, Hemachandra L A and Vyskˇoc J 1993 Complexity Theory (Ambos-Spies K, Homer S and Sch¨oning U, Eds.), Cambridge University Press, pp. 101–146
• [5] Hemachandra L 1993 Proc. 20 th Int. Colloquium on Automata, Languages and Programming; Lecture Notes in Computer Science 700 189
• [6] Ogihara M 1995 Inf. Proc. Lett. 54 41
• [7] Cintioli P and Silvestri R 1997 Theor. Comp. Systems 30 165
• [8] Bovet D P and Crescenzi P 1994 Introduction to the Theory of Complexity, Prentice-Hall, Englewood Cliffs, NJ
• [9] Balc´azar J L, D´ıaz J and Gabarr´o J 1988 Structural Complexity I, vol. 1, Springer Verlag
• [10] Johnson D S 1990 Handbook of Theoretical Computer Science (van Leeuwen J, Ed.) A, pp. 67–161
• [11] Beigel R, Hemachandra L and Wechsung G 1989 Proc. 4 th IEEE Structure in Complexity Theory Conference, University of Oregon, Eugene, Oregon, USA, pp. 225–227
• [12] Bovet D P, Crescenzi P and Silvestri R 1992 Theor. Comp. Sci. 104 263
• [13] Vereshchagin N K 1994 Russian Academy of Sciences. Izvestiya Mathematics (AMS) 42 261