%0 Journal Article
%T MNP: A class of NP optimization problems<br>MNP: A Class of NP Optimization Problems
%A Cheng Qi
%A and Zhu Hong
%A <br>Cheng Qi
%A Zhu Hong
%J 计算机科学技术学报
%D 1997
%I 
%X 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 nonapprokimability, so it is a more general version of L-reductions and A-reductions. Then some complete problems of this class under SL-reductions are shown and it is proved that the max-clique problem is one of them. So all complete problems in this class are as difficult to approximate as the max-clique problem.
%K Optimization problem
%K NP class
%K second-order logic
%K approximation algorithm
%K non-approximability<br>NP问题
%K 优化问题
%K 近似算法
%K 运筹学
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=739CE12BAD72203A73EFCA320CDA54FC&yid=5370399DC954B911&vid=59906B3B2830C2C5&iid=E158A972A605785F&sid=31BCE06A2FD82A16&eid=C2F76551C0111538&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=13