Definition
Strong NP-hardness
A computational problem is strongly NP-hard if it remains NP-hard even when all of its numerical parameters are bounded by a polynomial in the length of the input. Equivalently, a problem is strongly NP-hard if it remains NP-hard when all numbers in the input are encoded in unary.
This stands in contrast to weak NP-hardness, where the hardness depends on exponentially large numeric values when encoded in binary. Strongly NP-hard problems do not admit pseudo-polynomial time algorithms unless P = NP.
Characterisation
Strong NP-hardness indicates that the computational difficulty is intrinsic to the problem’s combinatorial or structural complexity, not merely a consequence of large numeric parameters. Even when all numbers are restricted to small constants (e.g., ), the problem remains intractable.
The standard technique for proving strong NP-hardness is to reduce from a known strongly NP-hard problem using only small constant values, or to reduce from a problem like 3-SAT where the hardness derives from dimensionality or structure rather than numeric magnitude.
Contrast with Weak NP-hardness
Weakly NP-hard problems become tractable when numbers are small (unary encoding). Strongly NP-hard problems remain hard regardless of encoding. The distinction is crucial:
- Weak: Hardness from numeric magnitude (exponential in binary representation)
- Strong: Hardness from combinatorial structure (persists with unary encoding)
Examples
- Travelling Salesman Problem: Strongly NP-hard. Remains hard regardless of edge weight magnitude.
- Vector Subset Sum Problem: Strongly NP-hard. The reduction from 3-SAT Problem uses only values , with hardness deriving from vector dimensionality rather than numeric size.
- 3-Partition Problem: Strongly NP-hard. Remains hard even when integers are polynomially bounded.
- Bin Packing Problem: Strongly NP-hard. The hardness persists with bounded bin capacities.G