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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ this is more a "symmetry" than an "anti symmetry" $\endgroup$– vznCommented Feb 21, 2013 at 17:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
$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.
-
$\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$– MirranaCommented Feb 20, 2013 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$– ShaullCommented Feb 20, 2013 at 21:02
-
$\begingroup$ I like that explanation... Thanks a lot. Hopefully it will help come my midterm exam on Friday. $\endgroup$– MirranaCommented Feb 20, 2013 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$– MirranaCommented Feb 21, 2013 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$– ShaullCommented Feb 22, 2013 at 0:25