The main emphasis in this project is the study of structural properties of complexity classes and complexity bounded reducibilities. The goal is to shed light on some of the major open problems involving the "natural" complexity classes and reducibilities specified by algorithms with polynomial bounds on their resources. Major emphasis will be placed on the problem of determining how results on relativizations for "almost every" oracle set should be interpreted. Specifically, the results of Bennett and Gill asserting that for almost every oracle set, the (full) relativizations of the classes P, NP, co-NP, and PSPACE form four different classes will be considered. This will be contrasted with recent results on characterization theorems for complexity classes specified by relativizations whose oracle access mechanism is restricted. The goal is to find general principles that will apply to a variety of questions about relationships among the natural complexity classes.
