# NP-Completeness and commutative property

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.

## 2 Answers

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.

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.