But unfortunately
the last result I will present now shows that maximum clique is not approximable
at all, so it does not belong to the class PTAS. How can I show you this result? I will do it by basically reducing the maximum SAT is reducible to maximum clique so that if maximum clique is in PTAS then the maximum SAT is in PTAS. Now we have just seen by applying the PCP theorem that maximum SAT is not in PTAS, hence from this theorem we have that maximum clique is not in PTAS. And if maximum clique is not in PTAS, this implies that maximum clique is not approximable at all. | ![]() |