Incomputational complexity,strong NP-completeness is a property of computational problems that is a special case ofNP-completeness. A general computational problem may have numerical parameters. For example, the input to thebin packing problem is a list of objects of specific sizes and a size for the bins that must contain the objects—these object sizes and bin size are numerical parameters.

A problem is said to be stronglyNP-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.^[1] A problem is said to be stronglyNP-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.^[2]

Normally numerical parameters to a problem are given inpositional notation, so a problem of input sizen might contain parameters whose size isexponential in n. If we redefine the problem to have the parameters given inunary notation, then the parameters must be bounded by the input size. Thus strong NP-completeness or NP-hardness may also be defined as the NP-completeness or NP-hardness of this unary version of the problem.

For example,bin packing is strongly NP-complete while the0-1 Knapsack problem is onlyweakly NP-complete. Thus the version of bin packing where the object and bin sizes are integers bounded by a polynomial remains NP-complete, while the corresponding version of the Knapsack problem can be solved inpseudo-polynomial time bydynamic programming.

From a theoretical perspective any strongly NP-hard optimization problem with a polynomially bounded objective function cannot have afully polynomial-time approximation scheme (orFPTAS) unless P = NP.^[3][4] However, the converse fails: e.g. if P does not equal NP,knapsack with two constraints is not strongly NP-hard, but has no FPTAS even when the optimal objective is polynomially bounded.^[5]

Some strongly NP-complete problems may still be easy to solveon average, but it's more likely that difficult instances will be encountered in practice.

Assuming P ≠ NP, the following are true for computational problems on integers:^[6]

• If a problem isweakly NP-hard, then it does not have aweakly polynomial time algorithm (polynomial in the number of integers and thenumber of bits in the largest integer), but it may have a pseudopolynomial time algorithm (polynomial in the number of integers and themagnitude of the largest integer). An example is thepartition problem. Both weak NP-hardness and weak polynomial-time correspond to encoding the input integers inbinary coding.

• If a problem isstrongly NP-hard, then it does not even have apseudo-polynomial time algorithm. It also does not have afully-polynomial time approximation scheme. An example is the3-partition problem. Both strong NP-hardness and pseudo-polynomial time correspond to encoding the input integers inunary coding.

• Strongly NP-complete problems
• Complexity classes
• Computational complexity theory