# NP-completeness: Reduce to or reduce from?

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$?

• 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! – jmite May 13 '14 at 19:28

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.

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. $Q$ known to be NP-hard, $P$ claimed to have a polytime algorithm.

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