STRONG NP-COMPLETENESS RESULTS - MOTIVATION, EXAMPLES, AND IMPLICATIONS
STRONG NP-COMPLETENESS RESULTS - MOTIVATION, EXAMPLES, AND IMPLICATIONS
复制标题
DOI：
10.1145/322077.322090
复制
发表时间：
1978-01-01
影响因子：
2.5
通讯作者：
JOHNSON, DS
中科院分区：
文献类型：
--
作者：
GAREY, MR;JOHNSON, DS
一个计算问题的np完备性常常被用来说明它的“难处理性”。然而，有一些np完备性问题，如PARTITION和KNAPSACK，被许多实践者认为是可处理的。其原因是，尽管没有已知的以多项式m为界的算法来求解它们，已知的算法以多项式为界，以输入长度和给定问题实例中最大数字的大小为界。对于其他NP完全问题，可以证明除非P= NP，否则不存在这样的“伪多项式调谐”算法。本文给出了证明这类“强”np -完备性结果的一个标准框架，综述了迄今为止证明的一些强np -完备性结果，并指出了这些结果在优化和近似上的一些注意事项
The NP-completeness of a computational problem~ s frequently taken to unply its" mtractabthty" However, there are certain NP-complete problems mvolvmg numbers, such as PARTITION and KNAPSACK, which are considered by many practitioners to be tractable The reason for this IS that, although no algontluns for solvmg them in tune bounded by a polynomial m the mput length are known, algorithms are known which solve them m tune bounded by a polynomial m the input length and the magmtude of the largest number an the given problem mstance. For other NP-complete problems mvolvmg numbers it can be shown that no such" pseudopolynomml tune" algonthra can exist unless P= NP. In this paper we provide a standard framework for stating and proving" strong" NP-completeness results of this sort, survey some of the strong NP-completeness results proved to date, and indicate some unphcauons of these results for both opumlzatlon and approximaUon algontluns