0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.