An alternative approach for proving the NP-hardness of optimization problems

摘要

We provide a new reduction-based approach for proving the NP-hardness of optimization problems and establish that it includes the "classical" approach as a special case. We apply our alternative approach to prove the NP-hardness of a problem for which the classical approach is not applicable. Besides, we construct a special case of the problem with the property that finding an optimal element takes polynomial time despite that computing the objective function values is NP-hard. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.