# How Reduction works in proving NP-Hard?

A problem $$X$$ is $$NP$$-Hard if for all $$Y \in NP$$, $$Y \leq_P X$$. Further, if a problem $$Z$$ is $$NP$$-Complete, and $$Z \leq_P X$$, then I can prove (rather mechanically) that $$X$$ is $$NP$$-Hard.

I also found that, for a given X, say TSP, to prove it is $$NP$$-Hard, we often find a ($$NP$$-Complete) Z say $$HAM-CYCLE$$ (Hamiltonian-Cycle), and try to show that $$HAM-CYCLE$$ can be reduced to a $$TSP$$ in polynomial time.

My confusion is, why don't we try to show that for each instance of $$TSP$$, there exists a corresponding instance of $$HAM-CYCLE$$. Specifically, what if there exists an instance of $$TSP$$, for which there is no corresponding instance in $$HAM-CYCLE$$! In this case, how can the prior knowledge about the hardness of $$HAM-CYCLE$$ help in inferring on TSP's hardness!

Note: I also had similar concerns with proving $$NP$$-complete class. However, since all $$NPC$$ are also $$NP$$, I felt, similar reduction of a known NPC problem to a given problem, say Q, works. However, for $$NP$$-hard case, a given problem X need not to be $$NP$$ at all.

My confusion is, [when proving that TSP is NP-hard by reduction from HAM-CYCLE] why don't we try to show that for each instance of TSP, there exists a corresponding instance of HAM−CYCLE.

Because it doesn't matter. Being able to solve TSP allows you to solve HAM-CYCLE. The fact that it also allows you to do some other stuff (solve the TSP instances that don't correspond to translations of HAM-CYCLE instances) isn't an issue.

For example, if I tell you that multiplying numbers allows you to compute yearly salary from monthly salary, you don't object that $$13\times 11$$ doesn't correspond to any such calculation.

• Sorry if I'm missing something trivial. The problem I'm trying to solve is to find out how hard is any $TSP$ (NOT trying to find out how hard is HAM-CYCLE using knowledge of $TSP$ ). All I know is how to solve HAM-CYCLE, and how to transform each HAM-CYCLE to a $TSP$. With this, we divide all instances of TSP into two sets $X_1$ and $\overline{X_1}$ where $X_1$ includes all instances reducible from HAM-CYCLE. Given this set-up, my understanding is that I can say all TSP instances in $X_1$ are as hard as HAM-CYCLE. But I'm not sure if I can comment something about those in $\overline{X_1}$. – KGhatak Jul 22 '19 at 14:59
• @KGhatak No, you can't say anything about $\overline{X_1}$. But TSP is still hard overall because its hardest instances let you solve HAM-CYCLE. – David Richerby Jul 22 '19 at 15:48
• @ David Richerby Thanks for the definiteness in your response. It helps big time. Wondering what happens if someone comes with a curious case of reducing a problem in $P$ to TSP! – KGhatak Jul 22 '19 at 17:22
• @KGhatak That's not very interesting. $\mathrm{P}\subseteq\mathrm{NP}$ and TSP is $\mathrm{NP}$-complete so we already know that every problem in $\mathrm{P}$ reduces to TSP. We have much more efficient ways of solving problems that are in $\mathrm{P}$, though. – David Richerby Jul 22 '19 at 18:11

Apparently, you are expecting the reduction between any two $$\mathsf{NP}$$-complete problems $$X$$ and $$Y$$ to be a one-to-one map (e.g., a bijection). The idea of a reduction, however, is irrelevant to having instances "correspond" to others. What reductions do give us is a hardness relation between problems (and not between individual instances). If $$A$$ and $$B$$ are problems and $$A$$ is reducible to $$B$$, then we expect $$B$$ to be harder than $$A$$; the idea is that, if there is an efficient algorithm which solves $$B$$, then we can also solve $$A$$ by reducing it to $$B$$ and running said algorithm. Completeness, then, corresponds to the notion of hardness equivalence: $$A$$ is reducible to $$B$$ and $$B$$ is reducible to $$A$$; that is, if $$A$$ is hard (resp., easy), then so is $$B$$, and vice-versa.

To give an example why we cannot generally expect reductions to be injective, surjective, or even bijective, let again $$X$$ to be $$\mathsf{NP}$$-complete and consider the problem $$Z = \{ (0, x) \mid x \in X \} \cup \{ (1, y) \mid y \in \{ 0,1 \}^\ast \}$$. Naturally, we can reduce $$X$$ to $$Z$$ by mapping each instance $$x$$ of $$X$$ to $$(0,x)$$; this does not give us a surjective map. Further, note $$Z$$ is also reducible to $$X$$: map $$(0,x)$$ to $$x$$ and $$(1,y)$$ to $$x'$$ where $$x' \in X$$ is a fixed (i.e., hard-coded) instance. This reduction is surjective, though not injective. As you can see, there is really no relation between what we expect from a reduction and injectivity or surjectivity.

• Given that the reductions are called "many-one", it's possible that the asker expects them to be merely surjective, rather than bijective. – David Richerby Jul 22 '19 at 11:36

If one has access to a polynomial algorithm solving $$X$$, then there exists a polynomial algorithm for $$Z$$. That's the main point of reductions for complexity classes. Problem $$X$$ is at least as hard as problem $$Z$$.

Another point to be made here is that the class $$NP$$ is about worst-case complexity, i.e. language $$X$$ can be $$NP$$-hard because some instances of $$X$$ are hard, even if they don't have any corresponding instances in $$Z$$.

• One of the implications of the 2nd para your statement is that, to prove TSP is NP-Hard, we don't need to prove 'every' instance of HAM-CYCLE is polynomial time reducible to TSP, rather proving 'any single' arbitrary instance of HAM-CYCLE is reducible to TSP is just enough. Don't think this implication is acceptable. – KGhatak Jul 20 '19 at 19:22
• I believe the first sentence is self-explanatory. You probably did not mean to write Z twice – user106386 Jul 20 '19 at 22:21
• user679128 - Not sure what the first sentence of 'diplodoc' trying to explain with regard to my confusion. The first para of 'diplodoc' merely re-states what I wrote in the first 2 paras in my question. I'm rather looking forward to some insight about my confusion mentioned in 3rd para. – KGhatak Jul 21 '19 at 4:32
• "How can the prior knowledge about the hardness of $HAM−CYCLE$ help in inferring on TSP's hardness". Suppose that TSP isn't hard (there exists a polynomial algorithm for it). Then, by combining this algorithm with polynomial reduction algorithm, one can derive a polynomial algorithm for $HAM-CYCLE$; a contradiction, assuming $P\neq NP$. It means that TSP is at least as hard as the hardest problem in $NP$, i.e. $NP-$hard. Whether or not there exists a one-to-one correspondence between the languages doesn't matter here. – diplodoc Jul 22 '19 at 9:49
• My second remark can be explained in the following way. Suppose, $Z \in NPC$, and there is a sub-language $Y \subseteq X$ s.t. there is a polynomial one-to-one map between $Z$ and $Y$. Let's assume that a map $Y$ onto $Z$ is also polynomial. It is obvious then that $Y\in NPC$. However, it may be the case that $X\in NP-hard \setminus NPC$ because of some instances outside of $Y$. – diplodoc Jul 22 '19 at 9:57