In this paper we show that the techniques introduced by Furst (1984), which connected oracle separation results for the relativized polynomial-time hierarchy to the problem of proving lower bounds for constant-depth circuits, and the subsequent probabilistic arguments introduced by Yao (1985), Hastad (1986), and Ko (1989), in order to prove the existence of relativized polynomial-time hierarchies with different structures, can be adapted for resolving the main problems related to the existence of immune and simple sets in the relativized polynomial-time hierarchy. In particular, we construct oracles which witness: 1. for any k>, the existence of a ΔPk-immune set in ΣPk; 2. for any k>, the existence of a Σk-simple set; 3. for any k>, the existence of a ΔPk-immune set in a relativized polynomial-time hierarchy for which ΣPk=ΠPk≠ΔPk; 4. for any k>1, the existence of a Σpk-1-immune set in a relativized polynomial-time hierarchy for which ΣPk=ΔPk;.

Strong separations of the polynomial hierarchy with oracles : constructive separations by immune and simple sets / D. Bruschi. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 102:2(1992), pp. 215-252.

Strong separations of the polynomial hierarchy with oracles : constructive separations by immune and simple sets

D. Bruschi
Primo
1992

Abstract

In this paper we show that the techniques introduced by Furst (1984), which connected oracle separation results for the relativized polynomial-time hierarchy to the problem of proving lower bounds for constant-depth circuits, and the subsequent probabilistic arguments introduced by Yao (1985), Hastad (1986), and Ko (1989), in order to prove the existence of relativized polynomial-time hierarchies with different structures, can be adapted for resolving the main problems related to the existence of immune and simple sets in the relativized polynomial-time hierarchy. In particular, we construct oracles which witness: 1. for any k>, the existence of a ΔPk-immune set in ΣPk; 2. for any k>, the existence of a Σk-simple set; 3. for any k>, the existence of a ΔPk-immune set in a relativized polynomial-time hierarchy for which ΣPk=ΠPk≠ΔPk; 4. for any k>1, the existence of a Σpk-1-immune set in a relativized polynomial-time hierarchy for which ΣPk=ΔPk;.
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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/2434/178470
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact