# How to show that a problem is easy?

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.

• You need to revisit the definitions. – Raphael Jan 25 '16 at 21:29

## 1 Answer

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

• Thank you. So what I understand is: If I want to show that a problem is easy, I have to reduce it, in polytime, to an easy problem. And if I want to show that a problem is hard, I have to reduce a hard problem, in polytime, to it. (Like the reverse way.) – 1-approximation Jan 25 '16 at 17:04
• That's exactly right. – Yuval Filmus Jan 25 '16 at 17:06