1
$\begingroup$

I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this notation can be reversed? that is, can I write this down like $A\ge_p B$ And still have a meaning? I searched a lot but this notation always been like the former and I got confused.

$\endgroup$
  • $\begingroup$ I have not encountered that notation before, so you should probably define it if you insist on using it. I'm not sure why you would want to write it down like this, but people will probably understand what you mean. (In fact, I personally find this notation a lot less clear than just natural language in most contexts) $\endgroup$ – Discrete lizard Apr 19 at 10:52
  • 1
    $\begingroup$ $A \geq B$ is the same as $B \leq A$. $\endgroup$ – Yuval Filmus Apr 19 at 11:01
  • $\begingroup$ In response to discrete lizard: it's about reducibility in the theory of computation $\endgroup$ – Daruis soli Apr 19 at 11:10
  • $\begingroup$ do you mean that A can be reduced to B in polynomial time? $\endgroup$ – lox Apr 19 at 11:25
  • 1
    $\begingroup$ Yes. I am writing an essay about difficulties of computing in another language( Farsi) and as you know, the writing style in this language is from right to left. in addition. I wanted to write this concept in an informal manner. then searching about this concept and its notation led me to believe that there is one way to writing this notation. although as you guys told, I'm in error and I can reverse it. $\endgroup$ – Daruis soli Apr 19 at 11:56
1
$\begingroup$

The notation $A \le_pB$ means problem $A$ can be reduced to problem $B$ in polynomial time, and that $B$ is at least as hard as $A$, because solving $B$ means solving $A$.

$A \le_pB$ $\equiv$ $B \ge_pA$

It does $\mathbf{not}$, however, mean $B \le_pA$, and to claim as much you would have to show the appropriate reduction.

$\endgroup$

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.