1978/07/01 by M. R. Garey, David Johnson · 4 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Scheduling and Optimization Algorithms #VLSI and Analog Circuit Testing #Citation #Completeness (order theory) #Computer science #Information retrieval #World Wide Web #Library science #Operations research #Mathematics
paper · pdf · doi:10.1145/322077.322090
openalex publication_date 1978/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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