5
$\begingroup$

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?

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

$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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mirrana Feb 20 '13 at 20:54
  • 1
    $\begingroup$ 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$). $\endgroup$ – Shaull Feb 20 '13 at 21:02
  • $\begingroup$ I like that explanation... Thanks a lot. Hopefully it will help come my midterm exam on Friday. $\endgroup$ – Mirrana Feb 20 '13 at 21:07
  • $\begingroup$ 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"? $\endgroup$ – Mirrana Feb 21 '13 at 19:52
  • $\begingroup$ "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). $\endgroup$ – Shaull Feb 22 '13 at 0:25

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.