3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You need to revisit the definitions. $\endgroup$ – Raphael Jan 25 '16 at 21:29
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – 1-approximation Jan 25 '16 at 17:04
  • $\begingroup$ That's exactly right. $\endgroup$ – Yuval Filmus Jan 25 '16 at 17:06

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.