Weak NP-completeness is a classification in computational complexity theory used to describe a subset of NP-complete problems that possess algorithms with pseudo-polynomial time complexity. A problem is considered weakly NP-complete if it is NP-complete but can be solved in time that is polynomial in the numerical magnitude of the input values, though it remains exponential relative to the binary length of those values.
The distinction between weak and strong NP-completeness depends on how numerical data within a problem instance affects its computational difficulty. In many NP-complete problems involving numbers, such as the knapsack problem, the subset sum problem, and the partition problem, the complexity is tied to the size of the integers involved. If these integers are represented in unary (where the length of the input is proportional to the value itself), the problems can be solved in polynomial time. However, when represented in standard binary or decimal notation, the input length is logarithmic relative to the values, making traditional polynomial-time solutions elusive.
An algorithm that runs in polynomial time relative to the numeric values of the input is said to run in pseudo-polynomial time. Weakly NP-complete problems are characterized by the existence of such algorithms, often implemented via dynamic programming. For instance, the knapsack problem can be solved using a dynamic programming approach that is efficient if the capacity of the knapsack or the weights of the items are relatively small.
In contrast, a problem is classified as strongly NP-complete if it remains NP-complete even when all of its numerical parameters are bounded by a polynomial in the length of the input. Examples of strongly NP-complete problems include the traveling salesperson problem and the vertex cover problem. These problems do not possess pseudo-polynomial time algorithms unless P = NP.
The formal framework for these distinctions was primarily established by Michael Garey and David S. Johnson. Their work highlighted that while all NP-complete problems are equivalent in terms of polynomial-time reductions, they vary significantly in their susceptibility to specific algorithmic techniques under certain constraints. Weak NP-completeness indicates that the "hardness" of the problem is specifically linked to the presence of large numerical values.