Definition
Weak NP-hardness
A computational problem is weakly NP-hard if it is NP-hard when its numerical inputs are encoded in standard binary (or higher base), but can be solved in polynomial time if its numerical inputs are encoded in unary.
Equivalently, a problem is weakly NP-hard if it admits a pseudo-polynomial time algorithm—an algorithm whose runtime is polynomial in the numeric value of the input rather than the bit-length. This implies the problem becomes tractable (i.e., in P) when the magnitude of the largest number is bounded by a polynomial in the input size.
Characterisation
Weak NP-hardness arises when the computational difficulty stems from the potential exponential size of numeric parameters when encoded in binary. The hardness is not intrinsic to the problem’s combinatorial structure but rather to the encoding efficiency. When numbers are small (unary encoding), the problem admits efficient solutions.
Contrast with Strong NP-hardness
A problem is strongly NP-hard if it remains NP-hard even when all numeric parameters are bounded by a polynomial in the input length (i.e., with unary encoding). Such problems do not admit pseudo-polynomial time algorithms unless P = NP.
The critical distinction: weakly NP-hard problems are hard due to large numbers; strongly NP-hard problems are hard due to structural complexity regardless of number magnitude.
Examples
- Subset Sum Problem: Weakly NP-hard. Solvable in via dynamic programming, which is polynomial in the unary size of but exponential in its binary representation.
- Knapsack Problem: Weakly NP-hard. Admits pseudo-polynomial dynamic programming solutions.
- Partition Problem: Weakly NP-hard. A special case of Subset Sum.