Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and therefore they sometimes hide the essential properties which ensure the obtained results. In order to obtain more general results, a uniform family of computation models which encompass most of the complexity classes of interest has been introduced in an earlier paper. As an initial set of results derivable from the proposed approach, a necessary and sufficient condition to prove the separation of relativized complexity classes, a characterization of complexity classes which admit a complete language, and a sufficient condition to prove the strong separation of relativized complexity classes have been presented in that paper. In this paper, we apply this approach to obtain positive relativization results, that is, results similar to those obtained in the literature. In particular, our goal is to prove statements of the kind: "Given two complexity classes C and D, C = D if and only if for every sparse set S, C^S = D^S." We derive a sufficient condition to prove such results and, as an application, we prove a general theorem from which all of the results obtained previously and new ones can be immediately derived.

COMPLEXITY CLASSES AND SPARSE ORACLES / D.P. BOVET; P. CRESCENZI; R. SILVESTRI. - STAMPA. - (1991), pp. 102-108. ((Intervento presentato al convegno SIXTH STRUCTURE IN COMPLEXITY THEORY CONFERENCE.

COMPLEXITY CLASSES AND SPARSE ORACLES

CRESCENZI, PIERLUIGI;
1991

Abstract

Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and therefore they sometimes hide the essential properties which ensure the obtained results. In order to obtain more general results, a uniform family of computation models which encompass most of the complexity classes of interest has been introduced in an earlier paper. As an initial set of results derivable from the proposed approach, a necessary and sufficient condition to prove the separation of relativized complexity classes, a characterization of complexity classes which admit a complete language, and a sufficient condition to prove the strong separation of relativized complexity classes have been presented in that paper. In this paper, we apply this approach to obtain positive relativization results, that is, results similar to those obtained in the literature. In particular, our goal is to prove statements of the kind: "Given two complexity classes C and D, C = D if and only if for every sparse set S, C^S = D^S." We derive a sufficient condition to prove such results and, as an application, we prove a general theorem from which all of the results obtained previously and new ones can be immediately derived.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference
SIXTH STRUCTURE IN COMPLEXITY THEORY CONFERENCE
D.P. BOVET; P. CRESCENZI; R. SILVESTRI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE 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/2158/237686
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact