Instances of optimization problems with multiple objectives can have several optimal solutions whose cost vectors are incomparable. This ambiguity leads to several reasonable notions for solving multiobjective problems. Each such notion defines a class of multivalued functions. We systematically investigate the computational complexity of these classes.

Some solution notions S turn out to be equivalent to NP in the sense that each function in S has a Turing-equivalent set in NP and each set in NP has a Turing-equivalent function in S. Other solution notions are equivalent to the function class NPMVg. We give evidence that certain solution notions are not equivalent to NP and NPMVg. In particular, under suitable assumptions there are functions in NPMVg that are Turing-inequivalent to all sets. It follows that the complexity of multiobjective problems is in general not expressible in terms of sets.

Moreover, we determine the possible combinations of complexities for every fixed multiobjective problem. In particular, for arbitrary A,B,C in NP such that A Turing-reduces to B and B Turing-reduces to C there is a multiobjective problem where one solution notion is Turing-equivalent to A, another one is Turing-equivalent to B, and a third one is Turing-equivalent to C.