6
$\begingroup$

Very simple question, but a mistake I make often enough that I'd love to have a standard reference.

I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve $P$, then showing that this solves another NP-Hard problem $Q$ in polynomial time.

Have I reduced $P$ to $Q$ or have I reduced $Q$ to $P$?

Since $Q$ is the problem of known hardness I've chosen, have I reduced from $Q$ or reduced to $Q$?

$\endgroup$
  • $\begingroup$ Just to clarify: I understand the concepts of NP-completeness and complexity theory. I really just can't remember when to use "from" and "to". Thanks for all the answers! $\endgroup$ – jmite May 13 '14 at 19:28
8
$\begingroup$

To show a new problem $X$ is hard, you reduce from a problem of known hardness to $X$. For example, you can show $X$ is hard by reducing 3-SAT to $X$.

The general idea is that if you had an efficient algorithm for solving $X$, you could also solve instances of 3-SAT efficiently. This is so because you can exhibit a polynomial time transformation from a 3-SAT instance to an instance of $X$. Given an instance of 3-SAT, you transform it into an instance of $X$, apply the efficient algorithm for $X$, and thus have solved the 3-SAT instance.

$\endgroup$
4
$\begingroup$

Suppose you already know that a problem $Q$ is NP-hard. Now you need to show that problem $P$ is NP-hard.

Note that it's very informal and intuitive idea.

We'll show $P$ is as hard as $Q$, which proves that $P$ is also Np-hard. We know that $Q$ is very hard problem. Now the idea is like proof by contradiction. Assume $P$ is not that hard like $Q$ and I could have an easy algorithm. Now, I need to get some contradiction. So what can I do? I can reduce $Q$ to $P$, i.e, we have an easy black box algorithm for $P$ and we can use that to change an input of $Q$ to input of $P$ and use that black box to get a solution for $Q$. Oh! I have easily solved $Q$. But, this contradicts the fact that $Q$ was hard. Thus our assumption was wrong and $P$ must be also as hard as $Q$.

The following image will not let you forgot the direction ever.

enter image description here

$Q$ known to be NP-hard, $P$ claimed to have a polytime algorithm.

$\endgroup$
3
$\begingroup$

Short answer: You have to reduce a known $\mathtt{NP}$-hard problem $Q$ to your problem $P$.

Let me give an informal argument why this is the case. Note that if you reduce $Q$ to $P$, then you can reduce any problem from $\mathtt{NP}$ to $P$. Thus $P$ is $\mathtt{NP}$-hard, by defintion of $\mathtt{NP}$-hardness. (A problem $Q$ is $\mathtt{NP}$-hard if every problem from $\mathtt{NP}$ is reducible to it. Equivalently, a problem is $\mathtt{NP}$-hard if there exists an $\mathtt{NP}$-complete problem that is reducible to it.)

I highly recommend Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.

Also, $\mathtt{NP}$-hardness is not the same as $\mathtt{NP}$-completeness. The title of the question asks for $\mathtt{NP}$-completeness, while the question itself is about $\mathtt{NP}$-hardness. The problem $Q$ is $\mathtt{NP}$-complete if it is $\mathtt{NP}$-hard and if it is in $\mathtt{NP}$. Note that $\mathtt{NP}$-hard problem need not be in $\mathtt{NP}$.

$\endgroup$

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.