1
$\begingroup$

Probably this is a basic question but I'm not sure how to finish this proof. I have a problem $X$ and I want to prove that it is possible to reduce $X$ to another problem $Y$. I know that $Y$ is NP-complete and that $Y$ can be reduced to $X$. Can I just conclude that $X$ is also NP-complete and thus $X$ can be reduced to $Y$? Is it necessary to show that $X$ is in NP?

$\endgroup$
1
$\begingroup$

You cannot conclude that.

Knowing that $Y$ is NP-complete and reduces to $X$ is only enough to conclude that $X$ is NP-hard.

To show that $X$ can be reduced to $Y$ you will have to either prove that $X\in NP$, or show a reduction directly (don't do this, it is probably harder than just solving $X$ itself).

$\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.