<p>To address your revised question:</p>

<blockquote>
  <p>If UGC is false, is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover?</p>
</blockquote>

<p>If it were known that it is NP-hard to approximate VC better than a factor of 2, even if the UGC is false, then we would unconditionally know that approximating VC to a factor better than 2 is NP-hard. This also works with a factor smaller than 2. If it were known that if UGC is false, then VC is NP-hard to approximate better than a factor of (say) 1.5, then we would know that it is (unconditionally) NP-hard to approximate it better than a factor of 1.5.</p>

<p>Since we don't know that, I guess the best we can say if the UGC is false is that it's NP-hard to approximate it to within a factor of 1.3606 by the result of <a href="http://annals.math.princeton.edu/2005/162-1/p08" rel="nofollow">Dinur and Safra (2005)</a>. (I think that's the current best-known inapproximability result.)</p>

CC BY-SA 3.0
2012-06-12T14:44:53.853Z
The first paragraph seems like a tautology, and I am not sure what it is supposed to explain.  I like the second paragraph.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-10T21:13:47.143Z
2012-06-10T21:13:47.143Z
Robin Kothari
<p>Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so <a href="http://en.wikipedia.org/wiki/Unique_games_conjecture" rel="nofollow">UGC</a> is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover, for example? If not, where does the new threshold of NP-hardness move in $(1,2-\epsilon]$?  </p>

CC BY-SA 3.0
2012-06-06T18:08:55.890Z
Hint: See a [blog post by Lance Fortnow about UG-hardness](http://blog.computationalcomplexity.org/2005/12/ug-hard.html).
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-06T18:41:14.947Z
Thank you Tsuyoshi, but I think the specific blog post is not related too much on a possible relation of UG with the NPI class, concerning inapproximability.
NicosM
CC BY-SA 3.0
2012-06-06T19:07:42.220Z
Nicos, the post actually is all about your question. In short, if UG is not in P, then there is no poly time algorithm which approximates max cut better than GW, etc.
Sasho Nikolov
CC BY-SA 3.0
2012-06-06T19:11:53.567Z
Sasho this is if UG is NP-hard. If UG is neither NP-hard nor in P, how do you know that? The conjecture clearly talks about the NP-hardness of unique games.
NicosM
CC BY-SA 3.0
2012-06-06T21:42:00.153Z
It would help if you are more specific about "the inapproximability results". Also what do you mean exactly by preserved? Do you mean we obtain exactly the same consequences?
Kaveh
CC BY-SA 3.0
2012-06-06T22:01:44.273Z
For example, whether the $(2-\epsilon)$ threshold for VC still holds, or the $0.878+\epsilon$ for Max-Cut.
NicosM
CC BY-SA 3.0
2012-06-06T23:42:22.453Z
That is the point of Lance's post: approximating MaxCut better than the GW constant is UG-hard, and this is a valid statement no matter if UGs are NP-hard. In other words, there is a polytime reduction which shows that if one can approximate MaxCut better than the GW constant, then the approximation algorithm can be used to solve UG in polytime. So if you cannot solve UG in polytime, you cannot approximage MaxCut better than GW
Sasho Nikolov
CC BY-SA 3.0
2012-06-10T17:36:36.973Z
Can you edit the question so that people can understand what you want to ask without reading the comment?
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-10T23:54:08.380Z
What do you mean by “threshold of NP-hardness”?  If you mean the boundary of approximation ratio between being NP-hard and not being NP-hard, then it should be obvious that without UGC, the results assuming UGC do not tell us anything about the boundary, and we do not know the exact value of the boundary without UGC.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-11T00:23:40.807Z
Yes that's what I mean. Therefore, he boundary stays 'somewhere' in [1.36,2-$\epsilon]$ and we can not deduce it, even if it is proved that $UG\in NPI$.
NicosM
<cc.complexity-theory><pcp><unique-games-conjecture>
Consequences of Unique Games being a NPI problem
NicosM
# Consequences of Unique Games being a NPI problem

(Asked by: username_0 on 2012-06-06)

Assume that UG is $\mathsf{NPI}$, i.e. not solvable in $\mathsf{P}$ nor in $\mathsf{NP\text{-}complete}$ (so [UGC](http://en.wikipedia.org/wiki/Unique_games_conjecture) is false). Is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover, for example? If not, where does the new threshold of NP-hardness move in $(1,2-\epsilon]$?

**Tags:** cc.complexity-theory, pcp, unique-games-conjecture

> **Comments:**
> **username_1**: Hint: See a [blog post by Lance Fortnow about UG-hardness](http://blog.computationalcomplexity.org/2005/12/ug-hard.html).  
> **username_0**: Thank you Tsuyoshi, but I think the specific blog post is not related too much on a possible relation of UG with the NPI class, concerning inapproximability.  
> **username_2**: Nicos, the post actually is all about your question. In short, if UG is not in P, then there is no poly time algorithm which approximates max cut better than GW, etc.  
> **username_0**: Sasho this is if UG is NP-hard. If UG is neither NP-hard nor in P, how do you know that? The conjecture clearly talks about the NP-hardness of unique games.  
> **username_3**: It would help if you are more specific about "the inapproximability results". Also what do you mean exactly by preserved? Do you mean we obtain exactly the same consequences?  
> **username_0**: For example, whether the $(2-\epsilon)$ threshold for VC still holds, or the $0.878+\epsilon$ for Max-Cut.  
> **username_2**: That is the point of Lance's post: approximating MaxCut better than the GW constant is UG-hard, and this is a valid statement no matter if UGs are NP-hard. In other words, there is a polytime reduction which shows that if one can approximate MaxCut better than the GW constant, then the approximation algorithm can be used to solve UG in polytime. So if you cannot solve UG in polytime, you cannot approximage MaxCut better than GW  
> **username_1**: Can you edit the question so that people can understand what you want to ask without reading the comment?  
> **username_1**: What do you mean by “threshold of NP-hardness”?  If you mean the boundary of approximation ratio between being NP-hard and not being NP-hard, then it should be obvious that without UGC, the results assuming UGC do not tell us anything about the boundary, and we do not know the exact value of the boundary without UGC.  
> **username_0**: Yes that's what I mean. Therefore, he boundary stays 'somewhere' in [1.36,2-$\epsilon]$ and we can not deduce it, even if it is proved that $UG\in NPI$.  

---

## 1 answers

### Answer by username_4 on 2012-06-10. Score: 4

To address your revised question:

> If UGC is false, is it still NP-hard to give a $(2-\epsilon)$ polytime approximation algorithm for Vertex Cover?

If it were known that it is NP-hard to approximate VC better than a factor of 2, even if the UGC is false, then we would unconditionally know that approximating VC to a factor better than 2 is NP-hard. This also works with a factor smaller than 2. If it were known that if UGC is false, then VC is NP-hard to approximate better than a factor of (say) 1.5, then we would know that it is (unconditionally) NP-hard to approximate it better than a factor of 1.5.

Since we don't know that, I guess the best we can say if the UGC is false is that it's NP-hard to approximate it to within a factor of 1.3606 by the result of [Dinur and Safra (2005)](http://annals.math.princeton.edu/2005/162-1/p08). (I think that's the current best-known inapproximability result.)

> **Comments:**
> **username_1**: The first paragraph seems like a tautology, and I am not sure what it is supposed to explain.  I like the second paragraph.  

---

