Toward a Unified Approach for the Classification of NP-Complete Optimization Problems

Toward a Unified Approach for the Classification of NP-Complete Optimization Problems
复制标题

DOI：
10.1016/0304-3975(80)90006-7
复制
发表时间：
1979-05
期刊：
Theor. Comput. Sci.
影响因子：
--
通讯作者：
G. Ausiello;A. Marchetti-Spaccamela;M. Protasi
G. Ausiello;A. Marchetti-Spaccamela;M. Protasi
中科院分区：
其他
文献类型：
--
作者：
G. Ausiello;A. Marchetti-Spaccamela;M. Protasi

文献摘要

被引文献

相似文献

两个概念已被引入的目的是分类NP完全优化问题进行比较：强NP完全性的概念，由于Garey和约翰逊，简单和刚性的问题，由于帕兹和莫兰。特别地，我们证明了在什么条件下约简保持刚性、简单性、强简单性和p-简单性，并证明了在合理的假设下，p-简单问题可以用伪多项式算法求解，强NP-完全问题是弱刚性的.
Two notions which have been introduced with the aim of classifying NP-complete optimization problems are compared: the notion of strong NP-completeness, due to Garey and Johnson, and that of simple and rigid problems, due to Paz and Moran. In particular, we show under what conditions reductions preserve rigidity, simplicity, strong simplicity andp-simplicity and we show that under reasonable hypothesis,p-simple problems are solved by pseudo-polynomial algorithms and strong NP-complete problems are weakly rigid.