Dureza UGC del predicado para ?

16

Antecedentes :

En el documento UGC original de Subhash Khot ( PDF ), demuestra la dureza de UG de decidir si una instancia de CSP dada con restricciones toda la forma No todo igual (a, b, c) sobre un alfabeto ternario admite una tarea satisfactoria 1 - de las restricciones o si no existen asignaciones que satisfagan de las restricciones, para arbitrariamente pequeño .8ϵϵ>089 9+ϵϵ>0 0

Tengo curiosidad por saber si este resultado se ha generalizado para cualquier combinación de restricciones -ary para y dominios variables de tamaño donde . Es decir,3 k 3 k 33k3k3

Pregunta :

¿Hay alguna dureza conocida de los resultados de aproximación para el predicado para para y ? norteUNmi(X1,...,X)XyosolF(k),k3k3

Estoy especialmente interesado en la combinación de valores ; por ejemplo, el predicado No todo igual ( ) para .=kX1,...,XkX1...,XksolF(k)

Daniel Apon
fuente
Por favor, una referencia para el caso ? k=3
Mohammad Al-Turkistany
@turkistany, después de analizar más mi pregunta, decidí eliminar la subpregunta (¡porque estaba preguntando demasiado de una vez!). Sin embargo, el documento al que me refería originalmente era este .
Daniel Apon
2
Si publica una pregunta sobre el artículo de Bulatov, tenga en cuenta que ha habido una simplificación significativa del enfoque durante la última década. Varios de los algoritmos se han simplificado y fusionado. Consulte el reciente documento LICS de Barto y Kozik para obtener una descripción general.
András Salamon
1
@Andras: ¿Asumo que quieres decir esto ? Se ve interesante; Definitivamente lo leeré, gracias! En cualquier caso, probablemente volveré a hacer la subpregunta anterior como una nueva pregunta pronto, suponiendo que no la responda por mí mismo (además, tengo poco tiempo para asegurarme de decirla correctamente en este momento) .
Daniel Apon
sí, ese es el Las referencias en este documento proporcionan un recorrido rápido por la historia posterior.
András Salamon el

Respuestas:

9

Me di cuenta de que lo que reclamé anteriormente es de hecho conocido.

Para y arbitrario , esto se encuentra en el documento FOCS 2002 de Khot "Dureza de colorear hipergrafías de 3 uniformes y 3 colores" (el documento en realidad habla del general , aunque el título solo habla de los 3 colores) caso).=3k3k

Para y , de hecho, se conoce una dureza más fuerte. Incluso si no hay de hecho una asignación de sólo dos valores a las variables que satisface todas las restricciones NAE (en otras palabras, el hypergraph Uniform se puede colorear utilizando 2 colores sin ningún hyperedge monocromática), todavía es NP-difícil encontrar una asignación de un tamaño de dominio k que satisface al menos 1 - 1 / k - 1 + ϵ restricciones NAE (para constante arbitraria ϵ > 04 4k2k1-1/ /k-1+ϵϵ>0 0) Esto se deduce fácilmente del hecho de que el resultado de inaplicabilidad conocido para la hiperposición de 2 colores da una fuerte declaración de densidad en el caso de solidez. La declaración formal aparece en mi artículo de SODA 2011 con Ali Sinop "La complejidad de encontrar conjuntos independientes en gráficos de grado (hiper) limitados de bajo número cromático" (Lemma 2.3 en la versión final de SODA y Lemma 2.8 en la versión anterior disponible en ECCC http://eccc.hpi-web.de/report/2010/111/ ).

Venkat Guruswami
fuente
Eso es muy hermoso Probablemente termine usando esto en un futuro muy cercano. ¡Gracias!
Daniel Apon
14

Llegué a esta página de una búsqueda sobre NAE-3SAT.

Estoy bastante seguro de que, para el problema que está planteando, debería ser NP-difícil saber si la instancia es satisfactoria, o si a lo sumo se puede satisfacer la fracción de restricciones. Es decir, un resultado de dureza ajustada (que coincide con lo que lograría simplemente elegir una asignación aleatoria), para instancias satisfactorias , y sin necesidad de UGC.1-1/ /k-1+ϵ

Para y 4 , esto se deduce del factor de Hastad 7/8 + resultado de inaplicabilidad épsilon para la división de 4 conjuntos (que luego se puede reducir a la división de conjuntos k para k > 4 ). Si las negaciones están bien, también se puede usar su resultado de dureza ajustada para Max ( - 1 ) -SAT.k=24 4k>4 4-1

Para , Khot demostró esto en un documento de FOCS 2002 "Dureza de la coloración de hipergrafías de 3 colores uniformes y 3 colores". (Es decir, eliminó la suposición original de UGC).k==3

=3k3Xyo+un,Xj+si,Xkun,si

Para el caso general, no sé si esto se ha escrito en alguna parte. Pero si realmente lo necesita, probablemente pueda encontrar algo o verificar el reclamo.

Venkat Guruswami
fuente
=4 4k
12

Prasad Raghavendra en su STOC'08 Best Paper demostró, asumiendo la Conjetura de Juegos Únicos, que un algoritmo de programación semidefinido simple proporciona la mejor aproximación para cualquier problema de satisfacción de restricciones (incluyendo NAE) con restricciones en un número constante de variables cada una y con un alfabeto constante. Para saber cuál es el factor de dureza para NAE, debe comprender qué tan bien lo hace el algoritmo simple, es decir, demostrar una brecha de integralidad para el programa. No sé si alguien ya hizo eso por NAE en toda su generalidad, o no.

Dana Moshkovitz
fuente
¡Oh Dios! También he pasado algunas lecturas de otras versiones del documento STOC de Raghavendra. ¡Debería haber hecho esta conexión! No sé si los valores NAE se han calculado específicamente tampoco, ¡pero definitivamente me interesarían!
Daniel Apon el