We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).

We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and to define corresponding NP-hardness notions. For both we prove reducibility and separation results.

Furthermore, we define approximative solution notions and investigate in which cases polynomial-time solvability translates from one to another notion. For problems where all objectives have to be minimized, approximability results translate from single-objective to multi-objective optimization such that the relative error degrades only by a constant factor. Such translations are not possible for problems where all objectives have to be maximized, unless P=NP.

As a consequence we see that in contrast to single-objective problems, where the solution notions coincide, the situation is more subtle for multiple objectives. So it is important to exactly specify the NP-hardness notion when discussing the complexity of multi-objective problems.