World's most popular travel blog for travel bloggers.

[Answers] How to show that a problem is easy?

, ,
Problem Detail:

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