By using this technique I will give you some examples of non-approximable results. In particular, I will show that it is not possible to approximate the minimum graph coloring problem, it is not possible to approximate TSP at all and also it is not possible to approximate the minimum bin packing problem within a performance ratio smaller than 3 over 2.
After this simple example we will need something more sophisticated. In particular we will need the so-called PCP theorem. By using this theorem we will be able to prove non-approximability results for the maximum satisfy ability problem. Starting for this non-approximability result it is possible to prove many other negative results.
