In this paper we analyze Ko's Theorem 3.4 in \cite{Ko87}. We extend point b) of Ko's Theorem by showing that $\poneh(\upcoup)=\upcoup$. As a corollary, we get the equality $\ph(\upcoup) = \poneh(\upcoup)$, which is, to our knowledge, a unique result of type $\poneh({\cal C})=\ph({\cal C})$, for a class $\cal C$ that would not be equal to $\DP$. With regard to point a) of Ko's Theorem, we observe that it also holds for the classes $\upk{k}$ and for $\fewp$. In spite of this, we prove that point b) of Theorem 3.4 fails for such classes in a relativized world. This is obtained by showing the relativized separation of $\upcoupk{2}$ from $\poneh(\npconp)$. Finally, we suggest a natural line of research arising from these facts.

Revisiting a result of Ko

CINTIOLI, Patrizio;
1997

Abstract

In this paper we analyze Ko's Theorem 3.4 in \cite{Ko87}. We extend point b) of Ko's Theorem by showing that $\poneh(\upcoup)=\upcoup$. As a corollary, we get the equality $\ph(\upcoup) = \poneh(\upcoup)$, which is, to our knowledge, a unique result of type $\poneh({\cal C})=\ph({\cal C})$, for a class $\cal C$ that would not be equal to $\DP$. With regard to point a) of Ko's Theorem, we observe that it also holds for the classes $\upk{k}$ and for $\fewp$. In spite of this, we prove that point b) of Theorem 3.4 fails for such classes in a relativized world. This is obtained by showing the relativized separation of $\upcoupk{2}$ from $\poneh(\npconp)$. Finally, we suggest a natural line of research arising from these facts.
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: http://hdl.handle.net/11581/116684
 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