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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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$ Commented Jul 22, 2019 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$ Commented Jul 22, 2019 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$ Commented Jul 22, 2019 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$ Commented Jul 22, 2019 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.

Improve this answer
$\endgroup$
1
  • 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$ Commented Jul 22, 2019 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$.

Improve this answer
$\endgroup$
5
  • $\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$ Commented Jul 20, 2019 at 19:22
  • $\begingroup$ I believe the first sentence is self-explanatory. You probably did not mean to write Z twice $\endgroup$ Commented Jul 20, 2019 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$ Commented Jul 21, 2019 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$ Commented Jul 22, 2019 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$ Commented Jul 22, 2019 at 9:57

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.