Dureza UGC do predicado para ?

16

Antecedentes :

No artigo UGC original de Subhash Khot ( PDF ), ele prova a dureza UG de decidir se uma determinada instância CSP com restrições de todo o formato Não igual a todos (a, b, c) ao longo de um alfabeto ternário admite uma tarefa que satisfaça 1 - das restrições ou se não existem atribuições que satisfaçam das restrições, por arbitrariamente pequenos .8ϵϵ>089+ϵϵ>0

Estou curioso para saber se esse resultado foi generalizado para qualquer combinação de restrições -ary para e domínios variáveis ​​de tamanho que . Isso é,l de 3 k 3 l de k 33k3k3

Pergunta :

Existem resultados de dureza conhecidos de aproximação para o predicado para para e ? x iG F ( k ) , k 3 k 3NAE(x1,,x)xiGF(k),k3k3

Estou especialmente interessado na combinação de valores ; por exemplo, o predicado Não é igual ( ) para .x 1 , , x k x 1, x kG F ( k )=kx1,,xkx1 1...,xkGF(k)

Daniel Apon
fonte
Por favor, uma referência para o caso ? k=3
Mohammad Al-Turkistany
@turkistany, depois de analisar minha pergunta mais adiante, decidi remover a sub-pergunta (porque estava perguntando demais de uma vez!). O artigo ao qual eu estava me referindo originalmente era esse .
Daniel Apon
2
Se você postar uma pergunta sobre o artigo de Bulatov, observe que houve uma simplificação significativa da abordagem na última década. Vários algoritmos foram simplificados e mesclados; veja o recente artigo do LICS de Barto e Kozik para uma visão geral.
András Salamon
11
@ Andras: Eu suponho que você quis dizer isso ? Parece interessante; Definitivamente vou ler, obrigado! De qualquer forma, provavelmente vou re-perguntar a sub-questão anterior como uma nova pergunta em breve, supondo que não responda por mim mesma (além disso, estou com pouco tempo para garantir que eu a declarei corretamente no momento) .
Daniel Apon 13/10/10
Sim, é esse. As referências nele fornecem um rápido passeio pela história subsequente.
András Salamon

Respostas:

9

Percebi que o que afirmei acima é de fato conhecido.

Para e k arbitrário 3 , isso está no artigo do FOCS 2002, de Khot, "Dureza da coloração de hipergrafos de 3 cores e 3 uniformes" (o artigo fala sobre k geral , embora o título fale apenas sobre o caso de 3 cores) .=3k3k

Para e k 2 , de facto, uma dureza mais forte é conhecido. Mesmo se houver de fato uma atribuição de apenas dois valores para as variáveis que satisfaz todas as restrições NAE (em outras palavras, o hipergrafo -uniform podem ser coloridos usando 2 cores sem qualquer hyperedge monocromática), ainda é NP-difícil encontrar uma atribuição de um tamanho de domínio k que satisfaça pelo menos 1 - 1 / k - 1 + ϵ restrições NAE (para constante arbitrária ϵ > 04k2k1 1-1 1/k-1 1+ϵϵ>0 0) Isso decorre facilmente do fato de que o resultado conhecido de inadequação para a coloração com hipergrafo 2 fornece uma forte declaração de densidade no caso da solidez. A declaração formal aparece em meu artigo da SODA 2011 com Ali Sinop "A complexidade de encontrar conjuntos independentes em gráficos limitados (hiper) de baixo número cromático" (Lema 2.3 na versão final do SODA e Lema 2.8 na versão mais antiga disponível no ECCC http://eccc.hpi-web.de/report/2010/111/ ).

Venkat Guruswami
fonte
Isso é muito bonito. Provavelmente vou acabar usando isso em um futuro muito próximo. Obrigado!
Daniel Apon
14

Cheguei nesta página a partir de uma pesquisa sobre o NAE-3SAT.

Tenho certeza de que, para o problema que você está perguntando, deve ser NP-difícil dizer se a instância é satisfatória ou se no máximo fração de restrições pode ser satisfeita. Ou seja, um resultado de dureza apertada (correspondendo ao que seria simplesmente escolher uma tarefa aleatória), para instâncias satisfatórias e sem necessidade do UGC.1 1-1 1/k-1 1+ϵ

Para e 4 , isso decorre do resultado da falta de aproximação de fator 7/8 + epsilon de Hastad para divisão de 4 conjuntos (que pode ser reduzida para divisão de k conjunto para k > 4 ). Se as negações estiverem corretas, também é possível usar o resultado de sua dureza para Max ( - 1 ) -SAT.k=24k>4-1 1

Para , Khot provou isso em um artigo da FOCS 2002 "Dureza da coloração de hipergrafos de 3 cores e 3 uniformes". (Ou seja, ele removeu a suposição original do UGC.)k==3

Para e k arbitrário 3 , Engebretsen e eu provamos esse resultado em "A satisfação com restrições sobre duas variáveis ​​é sempre fácil? Estrutura aleatória. Algoritmos 25 (2): 150-178 (2004)". No entanto, acho que nosso resultado exigiu "dobragem", ou seja, as restrições terão o formato NAE ( x i + a , x j + b , x k ) para algumas constantes a , b . (Este é o análogo de permitir negações de variáveis ​​booleanas.)=3k3xEu+uma,xj+b,xkuma,b

Para o caso geral, não sei se isso foi anotado em algum lugar. Mas se você realmente precisar, provavelmente posso encontrar algo ou verificar a reivindicação.

Venkat Guruswami
fonte
Obrigado pela ótima resposta! Eu desconhecia o último artigo que você vinculou (o seu com a Engebretsen) e isso definitivamente ajudará. Ainda estou interessado no caso geral (e encontrei uma situação semelhante: ela parece não estar escrita em lugar algum!). Mesmo algo para o caso e k arbitrário provavelmente forneceria informações suficientes. =4k
Daniel Apon
12

Prasad Raghavendra em seu Best Paper do STOC'08 provou, assumindo a Unique Games Conjecture, que um algoritmo de programação semidefinido simples fornece a melhor aproximação para qualquer problema de satisfação de restrições (incluindo NAE) com restrições no número constante de variáveis ​​e com alfabeto constante. Para realmente saber qual é o fator de dureza para o NAE, é necessário entender o desempenho do algoritmo simples, ou seja, provar uma lacuna de integralidade para o programa. Não sei se alguém já fez isso pelo NAE em sua generalidade total ou não.

Dana Moshkovitz
fonte
Oh que bom! Também passei lendo algumas outras versões do artigo STOC de Raghavendra. Eu deveria ter feito essa conexão! Também não sei se os valores NAE foram calculados especificamente, mas eles definitivamente me interessariam!
Daniel Apon