Problem Detail: I read somewhere that, if $Aleq_p B$ and $Bleq_p A$, then it is said that $Aequiv_p B$. What exactly does this mean? Is it saying that both $A$ and $B$ are the exact same level of complexity?
Asked By : agent154
Answered By : Shaull
$Aequiv_p B$ is by definition $Ale_p B$ and $Ble_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 $Ain LOGSPACE$ and $Bin NLOGSPACE$, then trivially $Aequiv_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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9985
