cc.complexity-theory – Una explicación puramente teórica de gráficos de la reducción de Unique Label Cover a Max-Cut

Pregunta:

Estoy estudiando la conjetura de los juegos únicos y la famosa reducción a Max-Cut de Khot et al. Desde su artículo y en otros lugares de Internet, la mayoría de los autores usan (lo que para mí es) una equivalencia implícita entre la reducción MAX-CUT y la construcción de pruebas particulares para códigos largos. Debido a mi propia falta de claridad sobre esa equivalencia, lucho por seguir este hilo de pensamiento.

También parece claro de estos planteamientos que se podría describir la reducción puramente en términos de gráficos, pero que por coincidencia o preferencia nadie elige hacerlo de esa manera. Por ejemplo, en estas notas de conferencia de O'Donnell, él insinúa que la prueba de código largo corresponde a una definición natural de los bordes en el gráfico que se está construyendo, pero como no está detallado, esa regla parece depender de la elección de un corte. para definir la función booleana que se está probando, y me ha dejado bastante confundido.

Así que le estoy pidiendo a alguien que explique la reducción "sólo" de forma gráfica en teoría. Creo que esto me ayudará a comprender la equivalencia entre los dos puntos de vista.

Respuesta:

Déjame ver si puedo aclarar esto, a un alto nivel. Suponga que la instancia de UG es un gráfico bipartito $ G = (V \ cup W, E) $, bijections $ \ {\ pi_e \} _ {e \ in E} $, donde $ \ pi_e \ colon \ Sigma \ to \ Sigma $ y $ | \ Sigma | = m $. Desea construir un nuevo gráfico $ H $ de modo que si la instancia de UG es $ 1- \ delta $ satisfactoria, entonces $ H $ tiene un corte grande, y si la instancia de UG ni siquiera es $ \ delta $ -satisfiable, entonces $ H $ tiene solo cortes muy pequeños.

El gráfico $ H $ contiene, para cada vértice en $ W $, una nube de $ 2 ^ m $ puntos, cada uno etiquetado por unos $ x \ in \ {- 1, 1 \} ^ \ Sigma $. La intención es que pueda interpretar una codificación de código larga de las etiquetas de $ W $ como un corte de $ H $. Recuerde que para codificar algo de $ \ sigma \ in \ Sigma $ con el código largo, usa una función booleana $ f \ colon \ {- 1, 1 \} ^ \ Sigma \ to \ {- 1, 1 \} $; en particular, es la función de dictador $ f (x) = x_ \ sigma $. Produzcamos un corte $ S \ cup T $ (es decir, bi-partición de los vértices) de la codificación del código largo de la siguiente manera. Si $ w \ in W $ tiene una etiqueta codificada por la función booleana $ f $, vaya a la nube de vértices en $ H $ correspondiente a $ w $, y ponga en $ S $ todos los vértices en la nube que están etiquetados por unos $ x $ para los cuales $ f (x) = 1 $. Todos los demás van a $ T $. Puede hacer esto al revés para asignar funciones booleanas a todos los $ w \ en W $ basándose en un recorte de $ H $.

Para que la reducción funcione, es necesario poder decir solo mirando el valor de un corte $ S \ cup T $ si las funciones booleanas correspondientes al corte están cerca de una codificación de código largo de alguna asignación de etiquetas a $ W $ que satisface muchas de las restricciones UG de $ G $. Entonces, la pregunta es qué información obtenemos del valor de un corte $ S \ taza T $. Considere dos vértices cualesquiera $ a $ con etiqueta $ x $ en la nube correspondiente a $ w $ y $ b $ con etiqueta $ y $ en la nube correspondiente a $ w '$ (en la reducción solo miramos $ w $, $ w '$ en diferentes nubes). Dijimos que el corte se puede usar para derivar funciones booleanas $ f_w $ y $ f_ {w '} $. Ahora, si hay una arista $ (a, b) $ en $ H $, entonces $ (a, b) $ se corta si y solo si $ f_w (x) \ neq f_ {w '} (y) $. Por lo tanto, usar solo el valor de un corte para saber si las funciones booleanas que induce son "buenas" es lo mismo que tener una prueba que, dadas las funciones booleanas $ \ {f_w \} _ {w \ in W} $, solo pregunta para qué fracción de alguna lista especificada de pares $ ((w, x), (w ', y)) $ tenemos $ f_w (x) \ neq f_ {w'} (y) $.

En otras palabras, siempre que Ryan dice en las notas "prueba si $ f_w (x) \ neq f_ {w '} (y) $", lo que realmente quiere decir es "en $ H $, agrega un borde entre el vértice en el nube de $ w $ etiquetada por $ x $ y el vértice en la nube de $ w '$ etiquetada por $ y $ ". Es decir, por cada $ v \ en V $, cada dos de sus vecinos $ w, w '$, y cada $ x, y \ in \ {- 1, 1 \} ^ n $, incluya el borde entre el vértice en el nube de $ w $ etiquetada por $ x \ circ \ pi_ {v, w} $ y el vértice en la nube de $ w '$ etiquetada por $ y \ circ \ pi_ {v, w'} $, y asigne la arista peso $ (({1- \ rho}) / {2}) ^ d (({1+ \ rho}) / {2}) ^ {nd} $ donde $ d $ es la distancia de Hamming entre $ x $ y $ y $. De esta manera, el valor de un corte dividido por el peso total del borde es exactamente igual a la probabilidad de éxito de la prueba.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım