21
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ +1 Very Nice. Thanks Tsuyoshi for shedding light on this important concept in complexity theory. $\endgroup$ – Mohammad Al-Turkistany Jun 11 '12 at 8:33
15
$\begingroup$

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

$\endgroup$
  • 8
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Jun 10 '12 at 16:49
  • 1
    $\begingroup$ @TsuyoshiIto you might consider accepting your own answer :). It's actually encouraged, and this is a good reference q/a for future googlers. $\endgroup$ – Suresh Venkat Jun 11 '12 at 15:18
  • $\begingroup$ @Suresh: Thanks. I probably will, but the system requires me to wait 48 hours after posting the question before accepting my own answer. $\endgroup$ – Tsuyoshi Ito Jun 11 '12 at 15:41
  • $\begingroup$ @TsuyoshiIto: Ah I didn't realize that. sounds good. $\endgroup$ – Suresh Venkat Jun 11 '12 at 15:49
  • $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Jun 11 '12 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.