Now we will introduce one of the main tool to prove negative results.
As in the case of decision problem we will introduce the notion of reducibility between two optimisation problems basically an approximation preserving reducibility which allows us to say that a problem A is easier to approximate than a problem B, in the sense that is we have an approximation algorithm for problem B that we can develop an approximation algorithm for problem A.
The notion of reducibility that we will introduce is the AP reducibility as a special case of AP reducibility and we will also define the reduction technique which as far as I know is the most used technique to prove reducibility among optimization problems.
I will give you several examples. For instance, I will be able to show that maximum clique and maximum independent set are not in the class APX, or that maximum 2-sat, maximum nae 3 sat, maximum sat(b), all these problems do not admit a polynomial time approximation scheme.