Clarifying what it means to be Strongly NP-Complete

Question

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?

Answer 1

Yes, that's correct. You'll probably have to figure out the polynomial yourself. The way to find the polynomial is to look at the reduction, and from that you should be able to deduce a polynomial.

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.