# Clarifying what it means to be Strongly NP-Complete

Wikipedia defines strongly NP-Complete as:

A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

What I interpret this to mean is this:

Let's consider the 3-partition problem, with our numerical paramater being $$\sum_{x \in S} x = B$$. Since this problem is strongly NP-Complete, there exists a polynomial $$p(N)$$, such that if we restrict ourselves to only sets $$S$$ such that $$B < p(|S|)$$, this problem is still NP-Complete. (i.e. finding an algorithm with complexity polynomial in $$|S|$$ for this restriction would prove P=NP)

Is this the correct interpretation? If so, where could I find upper bounds of such polynomials $$p$$ for famous problems, such as the 3-partition problem? Also, if I'm not mistaken, this implies that the 3-partition problem is NP-complete in terms of $$B$$, as well as $$|S|$$, right?

In your case, I believe there is a reduction from 3D-MATCHING to 3PARTITION, so you would analyze that reduction to find the polynomial. Given an instance of 3D-MATCHING, the reduction explicitly constructs an instance of 3PARTITION whose solution can be used to solve the 3D-MATCHING instance; so you'd analyze how large the parameter of 3PARTITION instance could possibly be, as a function of the size of the set, and that would tell you the polynomial $$p$$ you are looking for.