24

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

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

However, some people prefer to use the term “UG-hard” as:

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

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

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106

1 Answers1

17

An earlier version of this answer was originally posted as an answer to the question “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 > RGW.)

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

Community
  • 1
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • 9
    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 Jun 10 '12 at 16:49
  • 1
    @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 Jun 11 '12 at 15:18
  • @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 Jun 11 '12 at 15:41
  • @TsuyoshiIto: Ah I didn't realize that. sounds good. – Suresh Venkat Jun 11 '12 at 15:49
  • @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 Jun 11 '12 at 22:09
  • @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 Jun 11 '12 at 22:50