How do I prove the following statement?

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

  • 2
    $\begingroup$ 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. $\endgroup$ – Dmitry Nov 21 at 12:01
  • $\begingroup$ You cannot prove it since it's false. $\endgroup$ – 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$.

| cite | improve this answer | |

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.