Key points are not available for this paper at this time.
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
Garey et al. (Sat,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: