# What does “If P1 is reduced to P2, then P2 is at least as hard as P1” mean?

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.

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.
• @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. – Noah Schweber Jun 19 at 18:32