Complexity Classes and Sparse Oracles

摘要

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, CS = DS." 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.