В докладе будут рассмотрены классы сложности для задач комбинаторной оптимизации, такие как PO, NPO, APX, PTAS, FPTAS и будут показаны строгие включения NPO $\supset$ APX $\supset$ PTAS $\supset$ FPTAS.