Reduction of hard to easy problem and vice versa

91 Views Asked by At

$A\: \leq_m B$ means means $A$ cannot be harder than $B$ that means $B$ is atleast as hard as $A.$ And also I know that "If $B$ is easy then $A$ is easy" and "If $A$ is hard then $B$ is hard" But don't understand these two statements $:$

$(I)$ "If $B$ is hard then $A$ may or may not be hard. "

$(II)$ "If $A$ is easy then $B$ may or may not be easy."

1

There are 1 best solutions below

0
On BEST ANSWER

I believe it will help you to think of the $\leq_m$ relation as the usual $\leq$ ordering with "big" numbers being hard problems and "small" numbers being easy ones.

  • $(I)$ is saying that if $a \leq 10^{1000}$, for example, then $a$ may or may not be a "big" number ($1 \leq 10^{1000}$ but at the same time $10^{1000}-1 \leq 10^{1000}$).

  • $(II)$ on the other hand says that if $1 \leq b$, for example, then $b$ may or may not be a "small" number ($1 \leq 2$ but at the same time $1 \leq 10^{1000}$).