0
$\begingroup$

Consider a problem $X$ can be reduced to 3-partition problem. So, when 3-partition has a solution then $X$ has a solution. But if 3-partition does not have a solution, they $X$ may or may not have a solution. In this case, is it legal to say that the problem $X$ is np-complete?

$\endgroup$
3

1 Answer 1

3
$\begingroup$

No, that doesn't prove NP-completeness.

  1. The thing you describe isn't a reduction. It must be that the instance of $X$ has a solution if, and only if, the instance of 3-partition has a solution.

  2. Reducing $X$ to 3-partition just proves that $X$ is in NP. To prove completeness, you need to reduce an NP-complete problem to $X$.

I suggest that you revise the basic concepts from your class notes, textbook or online resources.

$\endgroup$
1
  • 2
    $\begingroup$ Just to add something to the previous answer (i can't comment yet :)) the reduction you are searching must be a polynomial time function (you can find some time expensive reductions from an Np-Complete problem to your problem X, however those are not making the NP-Complete problem any simpler!) $\endgroup$
    – doze
    Aug 5, 2016 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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