IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishIn 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;.
| Titolo: | Strong separations of the polynomial hierarchy with oracles : constructive separations by immune and simple sets |
| Autori: | BRUSCHI, DANILO MAURO (Primo) |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 1992 |
| Rivista: | |
| Tipologia: | Article (author) |
| Digital Object Identifier (DOI): | 10.1016/0304-3975(92)90232-5 |
| Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
http://hdl.handle.net/2434/178470
Copyright © 2019