We have the class PO, that is the class of efficiently solvable problems.
We have the class PTAS, that is the class of problems which admit a polynomial time algorithm for any performance ratio.
We have the class APT, that contain problems which are approximable for a given constant.
And then…. we do not know if there is something in the upper rectangle. We will see in the next lecture that it is sot empty.
