Schoning and Ko introduced respectively the concepts of helping and one-side-helping, and defined in this way new operators, ${\bf P}_{\rm help}(\cdot)$ and ${\bf P}_{\rm 1-help}(\cdot)$, acting on classes of sets $\cal C$ and returning classes of sets ${\bf P}_{\rm help}({\cal C})$ and ${\bf P}_{\rm 1-help}({\cal C})$. Subsequently, several results have been obtained on this subject, principally devoted to understanding how wide the classes ${\bf P}_{\rm help}({\cal C})$ and ${\bf P}_{\rm 1-help}({\cal C})$ are. For example, it seems that the ${\bf P}_{\rm help}(\cdot)$ operator contracts ${\bf NP}\cap co{\bf NP}$, while the ${\bf P}_{\rm 1-help}(\cdot)$ operator enlarges {\bf UP}. To obtain a better understanding of the relative power of ${\bf P}_{\rm 1-help}(\cdot)$ versus ${\bf P}_{\rm help}(\cdot)$ we propose to search, for every relativizable class ${\cal D}$ containing {\bf P}, the largest relativizable class $\cal C$ containing {\bf P} such that for every oracle $B$ ${\bf P}^B_{\rm help}({\cal C}^B)\se{\bf P}^B_{\rm 1-help}({\cal D}^B)$. In \cite{cs97b} it has been observed that ${\bf P}_{\rm help}({\bf UP}\cap co{\bf UP})= {\bf P}_{\rm 1-help}({\bf UP}\cap co{\bf UP})$, and this is true in any relativized world. In this paper we consider the case ${\cal D}={\bf UP}\cap co{\bf UP}$ and we show the existence of an oracle $A$ for which ${\bf P}^A_{\rm help}({\bf UP}_2^A\cap co{\bf UP}_2^A)$ is not contained in ${\bf P}^A_{\rm 1-help}({\bf UP}^A\cap co{\bf UP}^A)$. We prove also that that for every integer $k\geq 2$ there exists an oracle $A$ such that ${\bf P}^A_{\rm help}({\bf UP}^A_k\cap{\rm co}{\bf UP}^A_k)\not\se{\bf UP}^A_k$.}

Relativized Helping Operators

CINTIOLI, Patrizio
2005-01-01

Abstract

Schoning and Ko introduced respectively the concepts of helping and one-side-helping, and defined in this way new operators, ${\bf P}_{\rm help}(\cdot)$ and ${\bf P}_{\rm 1-help}(\cdot)$, acting on classes of sets $\cal C$ and returning classes of sets ${\bf P}_{\rm help}({\cal C})$ and ${\bf P}_{\rm 1-help}({\cal C})$. Subsequently, several results have been obtained on this subject, principally devoted to understanding how wide the classes ${\bf P}_{\rm help}({\cal C})$ and ${\bf P}_{\rm 1-help}({\cal C})$ are. For example, it seems that the ${\bf P}_{\rm help}(\cdot)$ operator contracts ${\bf NP}\cap co{\bf NP}$, while the ${\bf P}_{\rm 1-help}(\cdot)$ operator enlarges {\bf UP}. To obtain a better understanding of the relative power of ${\bf P}_{\rm 1-help}(\cdot)$ versus ${\bf P}_{\rm help}(\cdot)$ we propose to search, for every relativizable class ${\cal D}$ containing {\bf P}, the largest relativizable class $\cal C$ containing {\bf P} such that for every oracle $B$ ${\bf P}^B_{\rm help}({\cal C}^B)\se{\bf P}^B_{\rm 1-help}({\cal D}^B)$. In \cite{cs97b} it has been observed that ${\bf P}_{\rm help}({\bf UP}\cap co{\bf UP})= {\bf P}_{\rm 1-help}({\bf UP}\cap co{\bf UP})$, and this is true in any relativized world. In this paper we consider the case ${\cal D}={\bf UP}\cap co{\bf UP}$ and we show the existence of an oracle $A$ for which ${\bf P}^A_{\rm help}({\bf UP}_2^A\cap co{\bf UP}_2^A)$ is not contained in ${\bf P}^A_{\rm 1-help}({\bf UP}^A\cap co{\bf UP}^A)$. We prove also that that for every integer $k\geq 2$ there exists an oracle $A$ such that ${\bf P}^A_{\rm help}({\bf UP}^A_k\cap{\rm co}{\bf UP}^A_k)\not\se{\bf UP}^A_k$.}
2005
262
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11581/234717
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact