Uniformly defining complexity classes of functions

We introduce a general framework for the definition of function classes. Our model, which is based on polynomial time nondeterministic Turing transducers, allows uniform characterizations of FP, FP, counting classes (#·P, #·NP, #·coNP, GapP, GapP), optimization classes (max·P, min·P, max·NP, min·NP), promise classes (NPSV, #·P, c#·P), multivalued classes (FewFP, NPMV) and many more. Each such class is defined in our model by a certain family of functions. We study a reducibility notion between such families, which leads to a necessary and sufficient criterion for relativizable inclusion between function classes. As it turns out, this criterion is easily applicable and we get as a consequence e.g. that there are oracles A, B, such that min·P ⊈ #·NP, and max·NP ⊈ c#·coNP (note that no structural consequences are known to follow from the corresponding positive inclusions). © 1998 Springer-Verlag.