# Poly-time reduction is not antisymmetric

Lemma. (Transitivity) "$$\leq_p$$" is a transitive relation on languages, i.e., if $$L_1 \leq_p L_2$$ and $$L_2 \leq_p L_3$$, then $$L_1 \leq_p L_3$$.

Proof. By definition, there are poly-time functions $$f$$ and $$g$$ such that $$x \in L_1 \Leftrightarrow f(x) \in L_2$$ and $$y \in L_2 \Leftrightarrow g(y) \in L_3$$, thus $$x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3$$. Obviously, $$g(f(\cdot))$$ is poly-time (since $$|f(x)|$$ is polynomial in $$|x|$$).

This lemma proves that "$$\leq_p$$" is transitive, but how would I prove that it is not antisymmetric?

• What makes you think it's not reflexive? – jmite Feb 18 '18 at 18:17
• sorry meant only for antisymmetric! it is reflexive because f(w)=w satisfies that w ∈ L <=> f(w) ∈ L – crystyxn Feb 18 '18 at 18:20

By definition, a relation $R$ is antisymmetric if $aRb$ and $bRa$ implies $a=b$. Therefore, to show that $R$ is not antisymmetric, we have to find $a \neq b$ such that $aRb$ and $bRa$.
Specializing this to your case, you have to find two different languages $L_1 \neq L_2$ such that $L_1 \leq_p L_2$ And $L_2 \leq_p L_1$. Finding a pair of such languages isn't too challenging, so I leave it to you.