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

enter image description here

I would appreciate any insight on the matter. Thank you.


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.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your answer. Just to clarify -- does this mean that if P1 can be reduced to P2, and P1 can be solved in polynomial time, does this mean that so can P2? $\endgroup$ – drew181 Jun 19 at 17:41
  • $\begingroup$ @drew181 No - P2 is at least as hard as P1, not at least as easy as P1. Again, think in terms of numbers: "P1 can be reduced to P2" is analogous to "$p_1\le p_2$," and polytime-solvability is a "smallness" property. $\endgroup$ – Noah Schweber Jun 19 at 18:32

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.