First of all of course we introduce the formal definition of the optimization problems. This is clearly necessary because optimization problems will be the subject of this course.
Then we will relate the complexity of optimization problems with the complexity of their corresponding decision problems. For example we consider the problem of "maximum sat versus sat".
So we will see if there is a strict relation between this pair of problems. And this relation will then give evidence that many, hundreds and thousands optimization problems are not solvable in polynomial time. In this case evidence coincide with the following statement: "P different from NP".
If many, hundreds and thousands of opimization problems are not solvable in polynomial time we have to trait optimality for time complexity. This will lead us to the notion of approximation algorithms
