Topic summary
Strongly NP-complete
Extracted from the Wikipedia article Strong NP-completeness.
A problem is said to be strongly NP-complete (NP-complete in the strong sense), if it remains NP-complete even when all of its numerical parameters are bounded by a polynomial in the length of the input. A problem is said to be strongly NP-hard if a strongly NP-complete problem has a pseudo-polynomial reduction to it. This pseudo-polynomial reduction is more restrictive than the usual poly-time reduction used for NP-hardness proofs. In particular, the pseudo-polynomial reduction cannot output a numerical parameter that is not polynomially bounded by the size and value of numbers in the input.