COMPLEXITY CLASSES OF OPTIMIZATION FUNCTIONS

In this paper, complexity classes of functions defined via taking maxi ma or minima (cf. the work of Krentel) or taking middle elements (cf. the work of Toda) are examined. A number of axioms for a class to be a so-called p-founded class of optimization functions are given. it is shown that many natural function classes fulfill these axioms, Then th ese classes are examined concerning their relationship to complexity c lasses of sets. To this end, complexity preserving operators S and F f or encoding function classes into set classes and vice versa are intro duced. It is shown how these operators translate closure properties fr om one class to another, how they relate operators on classes of funct ions and classes of sets, and how they encode classes of maximum, mini mum, or median functions into well-studied classes of sets. The fixpoi nts of the compositional operator F . S are examined and shown to be e xactly those function classes ''closed under binary search.'' Let F-1 and F-2 be two such fixpoints, and H-1 and H-2 be their corresponding classes of sets (i.e., their images under the operator S). Then F-1 su bset of or equal to F-2 if and only if H-1 subset of or equal to H-2, and F-1 = F-2 if and only if H-1 = H-2. A number of natural classes of functions are shown to be such fixpoints. Thus we build hierachies of function classes with the same inclusional relationships as the polyn omial time hierarchy of sets and the counting hierarchy of sets, and w e prove many interesting structural properties of these hierarchies. ( C) 1995 Academic Press, Inc.