<p><em>An earlier version of this answer was originally posted as an answer to the question “<a href="https://cstheory.stackexchange.com/questions/11662/consequences-of-unique-games-being-a-npi-problem">Consequences of Unique Games being a NPI problem</a>” by NicosM.  Because it turned out that it did not answer what he wanted to ask, I moved it to this question.</em></p>

<p>Short answer: They mean different statements.  The latter implies the former, but the former does not necessarily imply the latter.</p>

<p>Long answer: Recall that the unique game problem is the following promise problem.</p>

<p><strong>Unique game problem with parameters <i>k</i>∈ℕ and <i>ε</i>, <i>δ</i> &gt; 0 (1−<i>ε</i> &gt; <i>δ</i>)</strong><br>
<em>Instance</em>: A two-player one-round unique game <i>G</i> with label size <i>k</i>.<br>
<em>Yes-promise</em>: <i>G</i> has value at least 1−<i>ε</i>.<br>
<em>No-promise</em>: <i>G</i> has value at most <i>δ</i>.</p>

<p>The unique games conjecture states:</p>

<blockquote>
  <p><strong>Unique games conjecture.</strong>  For all constants <i>ε</i> and <i>δ</i>, there exists a constant <i>k</i> such that the unique game problem with parameters <i>k</i>, <i>ε</i>, and <i>δ</i> is NP-complete.</p>
</blockquote>

<p>Consider results of the following form:</p>

<blockquote>
  <p>(1) Assuming the unique games conjecture, problem <i>X</i> is NP-hard.</p>
</blockquote>

<p>(An example of <i>X</i> is the problem of approximating maximum cut within some constant factor <i>R</i> &gt; <i>R</i><sub>GW</sub>.)</p>

<p>Most (if not all) of the results of the form (1) actually prove the following fact:</p>

<blockquote>
  <p>(2) There exist constants <i>ε</i> and <i>δ</i> such that for every constant <i>k</i>, the unique game problem with parameters <i>k</i>, <i>ε</i>, and <i>δ</i> is reducible to <i>X</i>.</p>
</blockquote>

<p>It is easy to verify that (2) implies (1).  However, (2) implies more than (1): for example, suppose that one day we can prove that a variant of the unique games conjecture where “NP-complete” is replaced with “<a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:G#gi" rel="nofollow noreferrer">GI</a>-hard.”  Then (2) implies that <i>X</i> is also GI-hard.  (1) does not imply this.  This is why some people consider that statement (1) is not the best way to state the theorem: (1) is weaker than what is actually proved, and the difference might be important.</p>

<p>Although (2) is a more accurate statement of what is proved, it is clearly mouthful.  This is why people have come up with a shorthand for it: “Problem <i>X</i> is UG-hard” is a shorthand for (2).</p>

CC BY-SA 3.0
2012-06-10T16:49:44.727Z
This seems analogous to the two statements: "(1) Assuming P != NP, X has no polynomial time algorithm" and "(2) X is NP-hard." (2) implies (1), but (1) doesn't imply (2). In practice, we usually prove (2), although we often say (1) to explain the significance of the proof to people unfamiliar with NP-hardness.
Robin Kothari
CC BY-SA 3.0
2012-06-11T15:18:18.320Z
@TsuyoshiIto you might consider accepting your own answer :). It's actually encouraged, and this is a good reference q/a for future googlers.
Suresh Venkat
CC BY-SA 3.0
2012-06-11T15:41:44.720Z
@Suresh: Thanks.  I probably will, but the system requires me to wait 48 hours after posting the question before accepting my own answer.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-11T15:49:19.483Z
@TsuyoshiIto: Ah I didn't realize that. sounds good.
Suresh Venkat
CC BY-SA 3.0
2012-06-11T22:09:00.400Z
@TsuyoshiIto: nice clear answer! sorry I didn't follow up on your request to make my comments an answer to the other question: I was party busy, part lazy, part didn't feel that the revised question was a question at all.
Sasho Nikolov
CC BY-SA 3.0
2012-06-11T22:50:11.573Z
@Sasho: Thanks, and no problem. I just wanted to tell you before I actually moved my answer so that you had a chance to post your comment as a separate answer if you wanted to, but I understand all the reasons you mentioned.  (I am not claiming that you are lazy. :))
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-10T15:23:37.450Z
2012-06-11T16:17:50.557Z
2017-04-13T12:32:28.167Z
Tsuyoshi Ito
<p>There are many inapproximability results which rely on the unique games conjecture.  For example,</p>

<blockquote>
  <p>Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a factor <i>R</i> for any constant <i>R</i> &gt; <i>R</i><sub>GW</sub>.</p>
</blockquote>

<p>(Here <i>R</i><sub>GW</sub> = 0.878… is the approximation ratio of the Goemans–Williamson algorithm.)</p>

<p>However, some people prefer to use the term “<a href="http://blog.computationalcomplexity.org/2005/12/ug-hard.html">UG-hard</a>” as:</p>

<blockquote>
  <p>It is UG-hard to approximate the maximum cut problem within a factor <i>R</i> for any constant <i>R</i> &gt; <i>R</i><sub>GW</sub>.</p>
</blockquote>

<p>Is the latter just a shorthand for the former, or do they mean different statements?</p>

CC BY-SA 3.0
2012-06-11T08:33:51.280Z
+1 Very Nice. Thanks Tsuyoshi for shedding light on this important concept in complexity theory.
Mohammad Al-Turkistany
<cc.complexity-theory><approximation-hardness><unique-games-conjecture>
What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?
Tsuyoshi Ito
# What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?

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

There are many inapproximability results which rely on the unique games conjecture. For example,

> Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a factor *R* for any constant *R* > *R*GW.

(Here *R*GW = 0.878… is the approximation ratio of the Goemans–Williamson algorithm.)

However, some people prefer to use the term “[UG-hard](http://blog.computationalcomplexity.org/2005/12/ug-hard.html)” as:

> It is UG-hard to approximate the maximum cut problem within a factor *R* for any constant *R* > *R*GW.

Is the latter just a shorthand for the former, or do they mean different statements?

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

> **Comments:**
> **username_1**: +1 Very Nice. Thanks Tsuyoshi for shedding light on this important concept in complexity theory.  

---

## 1 answers

### Answer by username_0 on 2012-06-10. Score: 17 | Accepted answer

*An earlier version of this answer was originally posted as an answer to the question “[Consequences of Unique Games being a NPI problem](https://cstheory.stackexchange.com/questions/11662/consequences-of-unique-games-being-a-npi-problem)” by NicosM. Because it turned out that it did not answer what he wanted to ask, I moved it to this question.*

Short answer: They mean different statements. The latter implies the former, but the former does not necessarily imply the latter.

Long answer: Recall that the unique game problem is the following promise problem.

**Unique game problem with parameters *k*∈ℕ and *ε*, *δ* > 0 (1−*ε* > *δ*)**  
*Instance*: A two-player one-round unique game *G* with label size *k*.  
*Yes-promise*: *G* has value at least 1−*ε*.  
*No-promise*: *G* has value at most *δ*.

The unique games conjecture states:

> **Unique games conjecture.** For all constants *ε* and *δ*, there exists a constant *k* such that the unique game problem with parameters *k*, *ε*, and *δ* is NP-complete.

Consider results of the following form:

> (1) Assuming the unique games conjecture, problem *X* is NP-hard.

(An example of *X* is the problem of approximating maximum cut within some constant factor *R* > *R*GW.)

Most (if not all) of the results of the form (1) actually prove the following fact:

> (2) There exist constants *ε* and *δ* such that for every constant *k*, the unique game problem with parameters *k*, *ε*, and *δ* is reducible to *X*.

It is easy to verify that (2) implies (1). However, (2) implies more than (1): for example, suppose that one day we can prove that a variant of the unique games conjecture where “NP-complete” is replaced with “[GI](http://qwiki.stanford.edu/index.php/Complexity_Zoo:G#gi)-hard.” Then (2) implies that *X* is also GI-hard. (1) does not imply this. This is why some people consider that statement (1) is not the best way to state the theorem: (1) is weaker than what is actually proved, and the difference might be important.

Although (2) is a more accurate statement of what is proved, it is clearly mouthful. This is why people have come up with a shorthand for it: “Problem *X* is UG-hard” is a shorthand for (2).

> **Comments:**
> **username_2**: This seems analogous to the two statements: "(1) Assuming P != NP, X has no polynomial time algorithm" and "(2) X is NP-hard." (2) implies (1), but (1) doesn't imply (2). In practice, we usually prove (2), although we often say (1) to explain the significance of the proof to people unfamiliar with NP-hardness.  
> **username_3**: @TsuyoshiIto you might consider accepting your own answer :). It's actually encouraged, and this is a good reference q/a for future googlers.  
> **username_0**: @Suresh: Thanks.  I probably will, but the system requires me to wait 48 hours after posting the question before accepting my own answer.  
> **username_3**: @TsuyoshiIto: Ah I didn't realize that. sounds good.  
> **username_4**: @TsuyoshiIto: nice clear answer! sorry I didn't follow up on your request to make my comments an answer to the other question: I was party busy, part lazy, part didn't feel that the revised question was a question at all.  
> **username_0**: @Sasho: Thanks, and no problem. I just wanted to tell you before I actually moved my answer so that you had a chance to post your comment as a separate answer if you wanted to, but I understand all the reasons you mentioned.  (I am not claiming that you are lazy. :))  

---

