Esboçando a Aproximabilidade de Todos os CSPs Finitos

Um problema de satisfação de restrições (CSP), \ (Max-CSP (F) \), é especificado por um conjunto finito de restrições \ (F qᵏ 0, 1 \) para inteiros positivos q e k. Uma instância do problema com n variáveis é dada por m aplicações de restrições de \ (F\) a subsequências das n variáveis, e o objetivo é encontrar uma atribuição para as variáveis que satisfaça o maior número de restrições. Na versão de (γ, β)-aproximação do problema para parâmetros 0 ≤ β ≤ γ ≤ 1, o objetivo é distinguir instâncias onde pelo menos uma fração γ das restrições pode ser satisfeita de instâncias onde no máximo uma fração β das restrições pode ser satisfeita. Neste trabalho, consideramos a aproximabilidade desse problema no contexto de algoritmos de esboço e fornecemos um resultado de dicotomia. Especificamente, para cada família \ (F\) e cada β < γ, mostramos que ou um algoritmo de esboço linear resolve o problema em espaço polilogarítmico ou o problema não é solucionável por nenhum algoritmo de esboço em \ (o (n) \) espaço. Em particular, apresentamos algoritmos de aproximação não triviais usando espaço polilogarítmico para infinitamente muitos problemas de satisfação de restrições. Também estendemos limites inferiores previamente conhecidos para algoritmos de streaming geral a uma ampla variedade de problemas, e em particular ao caso de q = k = 2, onde obtemos uma dicotomia, e ao caso em que as atribuições satisfatórias das restrições de \ (F\) suportam uma distribuição em \ (qᵏ\) com marginais uniformes. Antes deste trabalho, além de exemplos esporádicos, as únicas classes sistemáticas de CSPs que foram analisadas consideravam o cenário de variáveis booleanas q = 2, restrições binárias k = 2, e famílias unitárias \ (| F|=1\) e apenas consideravam o cenário onde as restrições eram impostas em literais, em vez de variáveis. Nossos resultados positivos mostram a ampla aplicabilidade de algoritmos baseados em viés usados anteriormente por 47 e 41, que estendemos para incluir algoritmos de estimação de norma mais ricos, fornecendo uma maneira sistemática de descobrir viéses. Nossos resultados negativos combinam os métodos analíticos de Fourier de 56, que estendemos a uma classe mais ampla de CSPs, com uma rica coleção de reduções entre problemas de complexidade de comunicação que estão no cerne dos resultados negativos. Em particular, trabalhos anteriores usaram análise de Fourier sobre o cubo booleano para iniciar seus resultados e os resultados pareciam particularmente adaptados a funções em literais booleanos (ou seja, com negações). Nossas técnicas surpreendentemente nos permitem chegar a CSPs gerais q-ários sem negações, apelando ao mesmo ponto de partida analítico de Fourier sobre hipercubos booleanos.