Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "oracle Turing machines" wg kryterium: Temat


Wyświetlanie 1-1 z 1
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ł
    Wyświetlanie 1-1 z 1

    Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies