Yes. If one of your multi-objective functions correspond to a NP-complete (decision problem) you can easily prove NP-Completeness: If you had an algorithm to solve

the Multi objective problem to optimality (i.e. finding the pareto-front), you could

take any single-dimension version of your NP-hard problem and add a constant

objective function. The use your multi-objective optimization algorithm and you have solved the NP complete problem.

@Fritz NP-hardness is a computational complexity result. Often it is what we need to warrant the use of approximation algorithms. Either way it doesn't hurt. One cannot know for sure if the problem will be NP-hard. I mean, I have spent the last year looking at cases of scheduling where some would seem NP-hard but actually are polynomial-time solvable, while others may surprise me and be intractable. One cannot say until they really prove it.

What context? Theoretical Computer Science, in particular, computational complexity is essential for categorizing optimization problems because under certain circumstances we can get a lovely reduction for example that leads to one of these problems being really the "same" as solving another problem even.

Hope this helps!

What is often forgotten about NP-hard problems is that it only proves asymptotic behavior. Hence even NP-hard problem MAY be solvable using a modern MIP solver (Cplex or Gurobi). As an example, I tried to see how large knapsack problems, which is weakly NP-hard, Cplex could solve under 5 minutes. Cplex (12.0) could solve problems with up to 4 million binary variables.

Hence, NP-hardness is a requirement to prove, before using approximation algorithm, BUT IT IS NOT ENOUGH. Test of the solution time using a MIP solver is also necessary, but often ignored.

The time-complexity for solving single-objective versions of the multi-objective problem is interesting, because some of the iterative approaches for finding the optimal pareto front assumes the possibility of solving the single-objective to optimality. The methods I am thinking about are the Two-Phase method and the Epsilon method.