How to show that a problem is easy?

Question

Let $P$ be a problem that you need to study its difficulty, i.e., NP-hard, Polynomial-time solvable, etc.

My question is: If I reduce a known polynomial time problem (say, maximum matching in bipartite graph) to $P$, why I can say that $P$ is an easy problem?

---

My guess is: No, we cannot say that.

Why? Because from an instance of maximum matching problem, $I_{ MM }$, I create an instance of $P$, $I_{ P }$, and then I show that maximum matching is solved with $I_{ MM }\iff P$ is solved with $I_{ P }$.

But what if from another instance of maximum matching problem, $I_{ MM }'$ , I create another instance of $P$, $I_{ P }'$, which is hard to solve?

I have read that the reduction is correct and works, for example from sorting to convex hull, but I do not why.

I do not know what I am missing here.

Answer 1

You are right. Any problem in $\mathsf{P}$ can be (polytime) reduced to the halting problem, for example. (In fact, any problem in $\mathsf{P}$ can be polytime reduced to any non-trivial language, that is any language other than $\emptyset$ or $\Sigma^*$.)

What is true is that if A reduces to B and B is easy, then so is A. In particular, if A polytime reduces to B and B is in $\mathsf{P}$, then A is also in $\mathsf{P}$.