<p>Reductions are defined with respect to the decision version of the problems.  Approximation ratios for their optimization versions are a separate question, which seems related but doesn't necessarily have to be.  So to answer your question with a question, from a philosophical perspective, why should you expect the class NPC to preserve approximation ratios when it isn't defined with respect to them in the first place?</p>

CC BY-SA 2.5
2011-01-12T04:12:53.930Z
"Reductions are defined with respect to the decision version of the problems." Is this true for, say [Levin reductions](http://planetmath.org/encyclopedia/LevinReduction.html)?
Sadeq Dousti
CC BY-SA 2.5
2011-01-12T14:55:55.490Z
You're right, not all reductions are defined w.r.t. decision versions, but we can define NPC only in terms of black-box reductions, and then I guess it can lead to debates about how these classes change w/ the reduction used...  I should have said "the class NPC is defined for decision problems."  It's not really a precise argument, as we could even define a class of decision problems whose optimization versions preserve approximation ratios, but that's not what we do for the class NPC. I guess given @N27's question is a philosophical objection, I'm allowed to give a philosophical response. :)
Lev Reyzin
CC BY-SA 2.5
2011-01-10T13:20:55.167Z
2011-01-10T13:20:55.167Z
Lev Reyzin
<p>Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar approximation ratios (referring to their optimization counterparts)? I guess that some constant or even polynomial drift might be understood but we have the case of constant-factor approximation algorithms for some NP-complete problems and, on the other hand, other problems that cannot be even approximated by a polynomial-ratio approximation algorithm, such as general TSP? Thank you</p>

CC BY-SA 2.5
2011-01-09T06:48:45.383Z
because the black box reductions only preserve the YES/NO aspect of the (decision) problems, not the closeness of the approximations.
Suresh Venkat
CC BY-SA 2.5
2011-01-09T07:06:10.407Z
@Suresh that is what I am asking. Why don't they preserve the approximation ratio, since they preserve the answer to the decision problem. In other words, what makes the structure of TSP, for example, (much) harder to approximate than that of Bin Packing, when they are both strong NP-complete problems and reducible to each other, so an answer to (D) TSP can be obtained by a black box solving (D) Bin Packing ? Thanks
N27
CC BY-SA 2.5
2011-01-09T08:45:48.830Z
if I reduce 3SAT to vertex cover, then vertex cover of size k implies satisfiability and vice versa. But if I get a vertex cover of size 2k, it doesn't mean I can satisfy half the clauses .
Suresh Venkat
CC BY-SA 2.5
2011-01-09T10:59:32.473Z
I would recommend Luca Trevisan's recent blog post here: http://lucatrevisan.wordpress.com/2011/01/05/cs261-lecture-1-overview/, in particular the example with Vertex Cover and Independent Set. (The last paragraph before Section 2.2)
Standa Zivny
CC BY-SA 2.5
2011-01-09T14:21:10.027Z
I think an intuition is asked for here. I can offer the following try based on the stated examples, without guaranty of correctness: Consider the "degrees of freedom" any "variable" in a problem has. In TSP, every node can come at any of $n$ (i.e. problem size) positions in the solution circle. For SAT, every variable can only have $2$ (i.e. constantly many) different values. For Bin Packing $k$ (i.e. independent of problem size $n$). It seems intuitive that TSP should be harder than the others.
Raphael
CC BY-SA 2.5
2011-01-09T14:24:37.710Z
Choose a specific reduction from one NP-complete problem to another, and try to extend it to preserve approximation ratios. You'll see what goes wrong.
Peter Shor 
CC BY-SA 2.5
2011-01-09T19:54:02.500Z
OK, thank you all for your answers. I understand and I already know what you mean to say from a mathematical point of view, but a "philosophical" skepticism will remain to me on that. Well anyway!...
N27
CC BY-SA 2.5
2011-01-09T20:12:09.177Z
Peter's answer is the best one really. Just try it and see what happens. I think by philosophical skepticism you mean 'I don't really get the intuition'. Sometimes the best way is just to try some examples and let the intuition grow.
Suresh Venkat
CC BY-SA 2.5
2011-01-10T14:35:49.640Z
Yet another way to grow your intuition: Take the vertex cover problem, and change the objective function. Minimise $\log |C|$ vs. $|C|$ vs. $|C|^2$ vs. $2^{|C|}$ over all vertex covers $C$. For each variant, the set of optimal solutions is exactly the same. However, some of the versions are much easier to approximate. The objective function of an optimisation is somewhat arbitrary, and approximability is highly dependent on the choice of the objective function. Indeed, the maximum independent set problem is just the minimum vertex cover problem with a strange objective function.
Jukka Suomela
CC BY-SA 2.5
2011-01-10T15:30:08.237Z
@Jukka, very nice, It makes a good answer.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-01-10T22:59:24.183Z
Also note that we can define approximation-preserving reductions: L-reductions, for example, preserve the approximation ratio up to a constant factor. See Papadimitriou & Yannakakis: "Optimization, Approximation, and Complexity Classes".
Zeyu
CC BY-SA 2.5
2011-01-12T02:56:52.250Z
@Jukka Indeed, before reading your comment I submitted a nearly identical answer (now deleted).
Alexandre Passos
<cc.complexity-theory><approximation-algorithms><reductions>
Why do NP-complete problems not have similar approximation ratios?
N27
# Why do NP-complete problems not have similar approximation ratios?

(Asked by: username_0 on 2011-01-09)

Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar approximation ratios (referring to their optimization counterparts)? I guess that some constant or even polynomial drift might be understood but we have the case of constant-factor approximation algorithms for some NP-complete problems and, on the other hand, other problems that cannot be even approximated by a polynomial-ratio approximation algorithm, such as general TSP? Thank you

**Tags:** cc.complexity-theory, approximation-algorithms, reductions

> **Comments:**
> **username_1**: because the black box reductions only preserve the YES/NO aspect of the (decision) problems, not the closeness of the approximations.  
> **username_0**: @Suresh that is what I am asking. Why don't they preserve the approximation ratio, since they preserve the answer to the decision problem. In other words, what makes the structure of TSP, for example, (much) harder to approximate than that of Bin Packing, when they are both strong NP-complete problems and reducible to each other, so an answer to (D) TSP can be obtained by a black box solving (D) Bin Packing ? Thanks  
> **username_1**: if I reduce 3SAT to vertex cover, then vertex cover of size k implies satisfiability and vice versa. But if I get a vertex cover of size 2k, it doesn't mean I can satisfy half the clauses .  
> **username_2**: I would recommend Luca Trevisan's recent blog post here: http://lucatrevisan.wordpress.com/2011/01/05/cs261-lecture-1-overview/, in particular the example with Vertex Cover and Independent Set. (The last paragraph before Section 2.2)  
> **username_3**: I think an intuition is asked for here. I can offer the following try based on the stated examples, without guaranty of correctness: Consider the "degrees of freedom" any "variable" in a problem has. In TSP, every node can come at any of $n$ (i.e. problem size) positions in the solution circle. For SAT, every variable can only have $2$ (i.e. constantly many) different values. For Bin Packing $k$ (i.e. independent of problem size $n$). It seems intuitive that TSP should be harder than the others.  
> **username_4**: Choose a specific reduction from one NP-complete problem to another, and try to extend it to preserve approximation ratios. You'll see what goes wrong.  
> **username_0**: OK, thank you all for your answers. I understand and I already know what you mean to say from a mathematical point of view, but a "philosophical" skepticism will remain to me on that. Well anyway!...  
> **username_1**: Peter's answer is the best one really. Just try it and see what happens. I think by philosophical skepticism you mean 'I don't really get the intuition'. Sometimes the best way is just to try some examples and let the intuition grow.  
> **username_5**: Yet another way to grow your intuition: Take the vertex cover problem, and change the objective function. Minimise $\log |C|$ vs. $|C|$ vs. $|C|^2$ vs. $2^{|C|}$ over all vertex covers $C$. For each variant, the set of optimal solutions is exactly the same. However, some of the versions are much easier to approximate. The objective function of an optimisation is somewhat arbitrary, and approximability is highly dependent on the choice of the objective function. Indeed, the maximum independent set problem is just the minimum vertex cover problem with a strange objective function.  
> **username_6**: @Jukka, very nice, It makes a good answer.  
> **username_7**: Also note that we can define approximation-preserving reductions: L-reductions, for example, preserve the approximation ratio up to a constant factor. See Papadimitriou & Yannakakis: "Optimization, Approximation, and Complexity Classes".  
> **username_8**: @Jukka Indeed, before reading your comment I submitted a nearly identical answer (now deleted).  

---

## 1 answers

### Answer by username_9 on 2011-01-10. Score: 7 | Accepted answer

Reductions are defined with respect to the decision version of the problems. Approximation ratios for their optimization versions are a separate question, which seems related but doesn't necessarily have to be. So to answer your question with a question, from a philosophical perspective, why should you expect the class NPC to preserve approximation ratios when it isn't defined with respect to them in the first place?

> **Comments:**
> **username_10**: "Reductions are defined with respect to the decision version of the problems." Is this true for, say [Levin reductions](http://planetmath.org/encyclopedia/LevinReduction.html)?  
> **username_9**: You're right, not all reductions are defined w.r.t. decision versions, but we can define NPC only in terms of black-box reductions, and then I guess it can lead to debates about how these classes change w/ the reduction used...  I should have said "the class NPC is defined for decision problems."  It's not really a precise argument, as we could even define a class of decision problems whose optimization versions preserve approximation ratios, but that's not what we do for the class NPC. I guess given @username_0's question is a philosophical objection, I'm allowed to give a philosophical response. :)  

---

