0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – KGhatak Jul 22 at 14:59
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Jul 22 at 15:48
  • $\begingroup$ @ 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! $\endgroup$ – KGhatak Jul 22 at 17:22
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Jul 22 at 18:11
2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – KGhatak Jul 20 at 19:22
  • $\begingroup$ I believe the first sentence is self-explanatory. You probably did not mean to write Z twice $\endgroup$ – user679128 Jul 20 at 22:21
  • $\begingroup$ 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. $\endgroup$ – KGhatak Jul 21 at 4:32
  • $\begingroup$ "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. $\endgroup$ – diplodoc Jul 22 at 9:49
  • $\begingroup$ 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$. $\endgroup$ – diplodoc Jul 22 at 9:57

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.