What does “If P1 is reduced to P2, then P2 is at least as hard as P1” mean?
-
29-09-2020 - |
Question
I am having trouble understanding the following statement regarding Turing reduction:
"If P1 is reduced to P2, then P2 is at least as hard as P1."
Does this mean that
(i) P2 can be harder or as hard as P1, or (ii) P2 can be easier or as hard as P1?
To represent this visually...
I would appreciate any insight on the matter. Thank you.
Solution
Interpretation (i) is correct: "$A$ is at least as hard as $B$" means that $A$ is as hard as or strictly harder than $B$. (Think about numbers: "$a$ is at least as big as $b$" means "$a=b$ or $a>b$.")
Note that not only does "$A$ is at least as hard as $B$" rule out $A$ being strictly weaker than $B$, it also rules out $A$ and $B$ being of incomparable complexity. Complexity isn't a linear order; we can find problems such that neither helps us solve the other.