¿Qué es la dureza UG y en qué se diferencia de la dureza NP en función de la conjetura de los juegos únicos?

Hay muchos resultados de inaplicabilidad que se basan en la conjetura de los juegos únicos. Por ejemplo,

Suponiendo la conjetura de los juegos únicos, es NP-difícil aproximar el problema de corte máximo dentro de un factor R para cualquier constante R > R _GW .

(Aquí R _GW = 0.878 ... es la relación de aproximación del algoritmo Goemans-Williamson).

Sin embargo, algunas personas prefieren usar el término " UG-hard " como:

Es difícil UG aproximar el problema de corte máximo dentro de un factor R para cualquier constante R > R _GW .

¿Es esto último solo una abreviatura de lo primero, o significan declaraciones diferentes?

NicosM publicó originalmente una versión anterior de esta respuesta como respuesta a la pregunta " Consecuencias de que los juegos únicos sean un problema de NPI ". Como resultó que no respondía lo que quería preguntar, lo moví a esta pregunta.

Respuesta corta: significan declaraciones diferentes. Lo último implica lo primero, pero lo primero no implica necesariamente lo segundo.

Respuesta larga: recuerde que el único problema del juego es el siguiente problema de promesa.

Problema de juego único con los parámetros k ∈ℕ y ε , δ > 0 (1− ε > δ )
Instancia : Un juego único de dos rondas G de dos jugadores con tamaño de etiqueta k .
Sí, prometo : G tiene un valor de al menos 1− ε .
Sin promesa : G tiene valor como máximo δ .

La conjetura de los juegos únicos dice:

Conjeturas de juegos únicos. Para todas las constantes ε y δ , existe una constante k tal que el único problema del juego con los parámetros k , ε y δ es NP-completo.

Considere los resultados de la siguiente forma:

(1) Suponiendo la conjetura de los juegos únicos, el problema X es NP-difícil.

(Un ejemplo de X es el problema de aproximar el corte máximo dentro de algún factor constante R > R _GW ).

La mayoría (si no todos) de los resultados del formulario (1) en realidad prueban el siguiente hecho:

(2) existen constantes varepsilon y delta tal que para cada constante k , el problema juego único con los parámetros k , ε , y δ es reducible a X .

Es fácil verificar que (2) implica (1). Sin embargo, (2) implica más que (1): por ejemplo, suponga que un día podemos demostrar que una variante de la conjetura de los juegos únicos donde "NP-complete" se reemplaza por " GI -hard". Entonces (2) implica que X también es GI-hard. (1) no implica esto. Esta es la razón por la cual algunas personas consideran que la afirmación (1) no es la mejor manera de establecer el teorema: (1) es más débil de lo que realmente se demuestra, y la diferencia podría ser importante.

Aunque (2) es una declaración más precisa de lo que se demuestra, es claramente bocado. Esta es la razón por la cual la gente se le ocurrió una taquigrafía: "El problema X es muy difícil" es una abreviatura de (2).