9400229 Selman This work will continue the research effort on the computational complexity of feasible computations. The objective is to distinguish properties of complexity classes that contain feasible computations from those that do not, to reveal the rich structure that individual complexity classes, such as NP, appear to have, and to increase understanding of the structural relations between low-level complexity classes. The emphasis will be to continue research on the complexity of multivalued computations and on relations between nonuniform and uniform complexity. The approach is the standard paradigm of structural complexity, that is, to elicit structural properties of complexity classes rather than analyze individual concrete problems. ***
