Qu'est-ce que la dureté UG et en quoi est-elle différente de la dureté NP basée sur la conjecture unique des jeux?

22

Il existe de nombreux résultats d'inapproximabilité qui reposent sur la conjecture unique des jeux. Par exemple,

En supposant la conjecture de jeux unique, il est difficile NP d'approximer le problème de coupe maximale dans un facteur R pour toute constante R > R GW .

(Ici, R GW = 0,878… est le rapport d'approximation de l'algorithme de Goemans – Williamson.)

Cependant, certaines personnes préfèrent utiliser le terme « UG-hard » comme:

Il est UG-difficile d'approximer le problème de coupe maximum dans un facteur R pour toute constante R > R GW .

Est-ce que ce dernier n'est qu'un raccourci pour le premier, ou signifie-t-il des déclarations différentes?

cc.complexity-theory approximation-hardness unique-games-conjecture Tsuyoshi Ito
la source
+1 Très agréable. Merci Tsuyoshi d'avoir mis en lumière cet important concept de la théorie de la complexité.
Mohammad Al-Turkistany

Réponses:

15

Une version antérieure de cette réponse a été initialement publiée comme réponse à la question « Conséquences des jeux uniques étant un problème NPI » par NicosM. Parce qu'il s'est avéré qu'il ne répondait pas à ce qu'il voulait demander, je l'ai déplacé vers cette question.

Réponse courte: ils signifient des déclarations différentes. Cette dernière implique la première, mais la première n'implique pas nécessairement la seconde.

Réponse longue: Rappelez-vous que le problème de jeu unique est le problème de promesse suivant.

Problème de jeu unique avec les paramètres k ∈ℕ et ε , δ > 0 (1− ε > δ )
Instance : Un jeu unique à deux joueurs G à un tour avec une taille d'étiquette k .
Oui, promesse : G a une valeur d'au moins 1− ε .
Pas de promesse : G a une valeur au plus δ .

La conjecture des jeux uniques déclare:

Conjecture de jeux uniques. Pour toutes les constantes ε et δ , il existe une constante k telle que le problème de jeu unique avec les paramètres k , ε et δ est NP-complet.

Considérez les résultats du formulaire suivant:

(1) En supposant la conjecture des jeux uniques, le problème X est NP-difficile.

(Un exemple de X est le problème de l'approximation de la coupe maximale à l'intérieur d'un facteur R > R GW constant .)

La plupart (sinon la totalité) des résultats du formulaire (1) prouvent en fait le fait suivant:

(2) Il existe des constantes e et ô telle que pour chaque constante k , le problème de jeu unique avec des paramètres k , ε et δ est réductible à X .

Il est facile de vérifier que (2) implique (1). Cependant, (2) implique plus que (1): par exemple, supposons qu'un jour nous pouvons prouver qu'une variante de la conjecture de jeux unique où «NP-complet» est remplacé par « GI- dur». Alors (2) implique que X est également GI-dur. (1) n'implique pas cela. C'est pourquoi certaines personnes considèrent que l'énoncé (1) n'est pas la meilleure façon d'énoncer le théorème: (1) est plus faible que ce qui est réellement prouvé, et la différence pourrait être importante.

Bien que (2) soit un énoncé plus précis de ce qui est prouvé, il est clairement gustatif. C'est pourquoi les gens ont trouvé un raccourci pour cela: «Le problème X est UG-difficile» est un raccourci pour (2).

Tsuyoshi Ito
la source
8
Cela semble analogue aux deux déclarations: "(1) En supposant que P! = NP, X n'a ​​pas d'algorithme de temps polynomial" et "(2) X est NP-difficile." (2) implique (1), mais (1) n'implique pas (2). En pratique, nous prouvons généralement (2), bien que nous disions souvent (1) pour expliquer la signification de la preuve à des personnes peu familiarisées avec la dureté NP.
Robin Kothari
1
@TsuyoshiIto vous pourriez envisager d'accepter votre propre réponse :). C'est en fait encouragé, et c'est une bonne référence pour les futurs googleurs.
Suresh Venkat
@Suresh: Merci. Je le ferai probablement, mais le système m'oblige à attendre 48 heures après avoir posté la question avant d'accepter ma propre réponse.
Tsuyoshi Ito
@TsuyoshiIto: Ah je ne m'en étais pas rendu compte. ça m'a l'air bien.
Suresh Venkat
@TsuyoshiIto: belle réponse claire! désolé, je n'ai pas donné suite à votre demande de faire de mes commentaires une réponse à l'autre question: j'étais partie occupée, en partie paresseuse, en partie je ne pensais pas que la question révisée était une question du tout.
Sasho Nikolov