# 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?

Posted on Categories proxies