# Anti-symmetry of polynomial time reductions

I read somewhere that, if $A\leq_p B$ and $B\leq_p A$, then it is said that $A\equiv_p B$. What exactly does this mean? Is it saying that both $A$ and $B$ are the exact same level of complexity?

• this is more a "symmetry" than an "anti symmetry" – vzn Feb 21 '13 at 17:26

$A\equiv_p B$ is by definition $A\le_p B$ and $B\le_p A$.

It means that they are in the "exact same level of complexity", but only with respect to polynomial time reductions! For example, if $A\in LOGSPACE$ and $B\in NLOGSPACE$, then trivially $A\equiv_p B$. But clearly $A$ and $B$ are not in the "same level of complexity".

This is part of a general observation about reductions: A reduction that is computable by a machine that works in $t(n)$ time (resp. $s(n)$ space) is only useful if you use it in classes that are provable at least as strong as $TIME[t(n)]$ (resp. $SPACE[s(n)]$), and are conjectured to be stronger.

So, polynomial time reduction are used in $NP$ and $PSPACE$, $LOGSPACE$ reductions are used in $NLOGSPACE$, etc.

• In the context of an assignment question I recently had, then... If I am given an arbitrary language $A$, and am asked to show that it is NP-Complete... do I need to pick a known NP-Complete problem $B$ and show that $A\leq_pB\wedge B\leq_pA$? If I understand correctly, $B\leq_pA$ only proves that $A$ is NP-Hard... but to bring it down into NP, I'd have to do the other way around, right? – Mirrana Feb 20 '13 at 20:54
• It is a possibility, but it is unnecessary. Indeed, if you show that $B\le_p A$, then $A$ is NP-hard. All that remains is to show that $A\in NP$. To do this, you can proceed in several ways: You can give a nondeterministic polynomial time algorithm for $A$, or you can show that $A$ has a polynomial time verifier (probably the easiest way), or you could show that $A\le_p C$ for some problem $C\in NP$ (not necessarily $B$). – Shaull Feb 20 '13 at 21:02
• I like that explanation... Thanks a lot. Hopefully it will help come my midterm exam on Friday. – Mirrana Feb 20 '13 at 21:07
• Something else: Could you elaborate a bit more on that? I'd like to write this down properly for a collection of notes I'm taking on the subject. Or where could I find more details about this? How is $\equiv_p$ read? I'm guessing "is polynomial-time equivalent to"? – Mirrana Feb 21 '13 at 19:52
• "is polynomial time equivalent" sounds about right. This is not a common notation, since all NP-complete problems are polynomial time equivalent. Thus, we just prove NP-completeness, rather than stating this equivalence. I don't know of any problems that are $\equiv_p$ without knowing that they are complete w.r.t some class (e.g. NP, PSPACE, etc). – Shaull Feb 22 '13 at 0:25