2
$\begingroup$

If $X$ is NP-complete and for some $Y, X\leq_p Y$ and $Y\leq_p X$ what can we say about $Y$?

My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.

$\endgroup$
0
2
$\begingroup$

Your property holds for, for example 3-SAT and 3-COLOURABILITY so it's certainly not required that $X=Y$.

The fact that $Y\leq_p X$ and $X\in\mathrm{NP}$ tells you that $Y\in\mathrm{NP}$; the fact that $X$ is $\mathrm{NP}$-complete and $X\leq_p Y$ tells you that $Y$ is $\mathrm{NP}$-hard. Therefore, $Y$ is $\mathrm{NP}$-complete.

$\endgroup$
2
$\begingroup$

Since $X$ is NPC and reduces in polynomial time to $Y$, we have that $Y$ is also NPC as nicely explained in David's answer. Further, since $Y$ is also reducible in polynomial time to $X$, we say that $X$ and $Y$ are polynomially equivalent.

It is not at all true that $X$ would have to equal $Y$ in order for $X$ and $Y$ to be polynomially equivalent. You can find a good amount of examples from e.g., graph theory by just searching with this term.

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