Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
this is more a "symmetry" than an "anti symmetry" –  vzn Feb 21 '13 at 17:26

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
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? –  agent154 Feb 20 '13 at 20:54
1  
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. –  agent154 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"? –  agent154 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.