# Polynomial time reducibility is an equivalence relation

How do I prove the following statement?

The relation $$≤_p$$ (polynomial time reduction) is an equivalence relation.

• Polynomial time reduction is not an equivalence relation. Try to come up with a counterexample. Also, always show your work, not just the problem statement. – Dmitry Nov 21 at 12:01
• You cannot prove it since it's false. – Yuval Filmus Nov 21 at 12:08

A polynomial-time reduction from $$A$$ to $$B$$ is a polynomial-time computable function $$f$$ that maps an instance $$x$$ of a problem (language) $$A$$ to an instance $$f(x)$$ of a problem $$B$$ such that $$x \in A \iff f(x) \in B$$.
Polynomial-time (Karp) reductions are reflexive (since $$A \le_p A$$), as it follows by choosing $$f(x) = x$$.
Polynomial-time reductions are transitive, i.e, if $$A \le_p B$$ and $$B \le_p C$$ then $$A \le_p C$$ by choosing $$f = h \circ g$$, where $$g$$ (resp. $$h$$) is a polynomial-time computable function such that $$x \in A \iff g(x) \in B$$ (resp. $$x \in B \iff h(x) \in C)$$.
However, Polynomial-time reductions are not reflexive. That is, it is not true that $$A \le_p B \implies B \le_p A$$. Consider for example a binary alphabet, $$A = \{0,1\}^*$$, and $$B = \{0\}$$. The function $$f(x) =0$$ is a valid polynomial-time reduction from $$A$$ to $$B$$ but there is no polynomial-time reduction from $$B$$ to $$A$$.