MNP: A class of NP optimization problems

摘要

A large class of NP optimization problems called MNP are studied. It is shown that Rmax(2) is in this class and some problems which are not likely in Rmax (2) are in this class. A new kind of reductions, SL-reductions, is defined to preserve approximability and nonapproximability, so it is a more general version of L-reductions and A-reductions. Then some compete problems of this class under SL-reductions are shown and it is proved that the max-clique problem is one of them.