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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Problems don't have solutions, problem instances do. You seem to be confused with the fundamentals; our reference questions can help. $\endgroup$– RaphaelCommented Aug 5, 2016 at 7:52
-
1$\begingroup$ It is not illegal to make false mathematical statements. $\endgroup$– Tom van der ZandenCommented Aug 5, 2016 at 9:33
-
1$\begingroup$ @TomVanDerZanden Put the statement down. Step away from the statement. Sorry, couldn't resist... :-D $\endgroup$– JuhoCommented Aug 5, 2016 at 13:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
No, that doesn't prove NP-completeness.
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.
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.
answered Aug 5, 2016 at 7:46
-
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$– dozeCommented Aug 5, 2016 at 19:58