O Gap-3SAT NP está completo mesmo para as fórmulas 3CNF em que nenhum par de variáveis ​​aparece em cláusulas significativamente mais que a média?

32

Nesta pergunta, uma fórmula 3CNF significa uma fórmula CNF em que cada cláusula envolve exatamente três variáveis distintas . Para um constante 0 < s <1, Gap-3SAT s é o seguinte problema de promessa:

Gap-3SAT s
Instância : Um 3CNF fórmula φ.
Sim, prometo : φ é satisfatório.
Sem promessa : nenhuma atribuição de verdade satisfaz mais que a fração s das cláusulas de φ.

Uma das maneiras equivalentes de afirmar o célebre teorema do PCP [AS98, ALMSS98] é que existe uma constante 0 < s <1, de modo que Gap-3SAT s é NP completo.

Dizemos que uma fórmula 3CNF é limitada em pares por B se cada par de variáveis ​​distintas aparecer na maioria das cláusulas B. Por exemplo, uma fórmula 3CNF ( x 1x 2x 4 ) ∧ (¬ x 1 ∨¬ x 3x 4 ) ∧ ( x 1x 3 ∨¬ x 5 ) é em pares 2-delimitada mas não aos pares 1 -bounded porque, por exemplo, o par ( x 1 , x 4 ) aparece em mais de uma cláusula.

Pergunta . Fazer existem constantes B ∈ℕ, um > 0, e 0 < s <1 tais que Gap-3SAT s é NP-completo, mesmo para uma fórmula 3CNF que é par a par B -bounded e consiste de pelo menos um 2 cláusulas, onde n é o número de variáveis?

A delimitação por pares implica claramente que existem apenas cláusulas O ( n 2 ). Juntamente com o limite inferior quadrático do número de cláusulas, ele diz aproximadamente que nenhum par de variáveis ​​distintas aparece em significativamente mais cláusulas que a média.

Para o Gap-3SAT, sabe-se que o caso escasso é difícil : existe uma constante 0 < s <1, de modo que o Gap-3SAT s é NP-completo, mesmo para uma fórmula 3CNF em que cada variável ocorre exatamente cinco vezes [Fei98]. Por outro lado, o caso denso é fácil : o Max-3SAT admite um PTAS para uma fórmula 3CNF com Ω ( n 3 ) cláusulas distintas [AKK99] e, portanto, o Gap-3SAT s neste caso está em P para cada constante 0 < s <1. A pergunta é sobre o meio desses dois casos.

A questão acima surgiu originalmente em um estudo da complexidade computacional quântica, mais especificamente, sistemas interativos de prova de dois provadores e uma rodada com provadores entrelaçados (sistemas MIP * (2,1) ). Mas acho que a questão pode ser interessante por si só.

Referências

[AKK99] Sanjeev Arora, David Karger e Marek Karpinski. Esquemas de aproximação de tempo polinomial para instância densa de problemas NP-hard. Journal of Computer and System Sciences , 58 (1): 193-210, fevereiro de 1999. http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudão e Mario Szegedy. Verificação de prova e dureza dos problemas de aproximação. Journal of the ACM , 45 (3): 501–555, maio de 1998. http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora e Shmuel Safra. Verificação probabilística de provas: Uma nova caracterização de NP. Journal of the ACM , 45 (1): 70–122, janeiro de 1998. http://doi.acm.org/10.1145/273865.273901

Uriel Feige. Um limite de ln n para aproximar a cobertura do conjunto. Journal of the ACM , 45 (4): 634–652, julho de 1998. http://doi.acm.org/10.1145/285055.285059

Tsuyoshi Ito
fonte
@ Tsuyoshi: estou certo ao presumir que nada se sabe sobre os outros casos intermediários, entre e m = Ω ( n 3 ) ? m=O(n)m=Ω(n3)
András Salamon
11
@ András: Não conheço nenhum resultado anterior sobre casos intermediários, mas tenho o que acho que é uma prova da completude do NP dos seguintes casos. (1) Pairwise delimitada, cláusulas, mas sem um intervalo. (2) Com uma lacuna, Ω ( n d ) cláusulas para qualquer constante d <3, mas não necessariamente em pares. (3) Com um intervalo, delimitado por pares, Ω ( n d ) cláusulas para qualquer constante d <2. A prova de (1) é uma simples redução de [Fei98]. A prova de (2) usa parte do resultado de Ailon e Alon 2007 . A prova de (3) usa expansores. Ω(n2)Ω(nd)Ω(nd)
Tsuyoshi Ito
11
@ Tsuyoshi: Ansioso para ler o seu artigo.
András Salamon
4
Não tenho uma resposta, mas gostaria de verificar se os métodos para certificar que um 3CNF aleatória de cláusulas M é insatisfatível pode ter sucesso aqui em mostrar esse problema é fácil, pelo menos se você exigiu a solidez para estar perto de 7/8. Esses trabalhos são bem-sucedidos quando há mais de n 1,5 cláusulas e foram estendidos a modelos semi-aleatórios (consulte Feige FOCS 07 sobre refinação de 3CNF suavizado). No entanto, parece que Tsuyoshi mostrou que mesmo o caso de n 1.9 aqui ainda é difícil para NP, então talvez isso mostre que esses trabalhos não são relevantes. sn1.5n1.9
Boaz Barak
7
Boaz, você sempre pode "densificar" uma instância do 3SAT substituindo todas as variáveis ​​por cópias e, em seguida, substituindo cada cláusula pelas cláusulas M 3 , substituindo cada variável na cláusula original por cópias de todas as maneiras possíveis. Isto dá-lhe um exemplo em que a mesma fracção de cláusulas como antes de ser satisfeita, mas ir de n variáveis e cláusulas m para nM variáveis e m M 3 cláusulas, assim, sem mais nenhuma restrição quanto ao número de ocorrências, é possível manter a solidez 7 / 8 + ε mesmo em fórmulas com N variáveis e N 2.999 cláusulas. MM3mM37/8+ϵNN2999
Luca Trevisan

Respostas:

6

Não é uma resposta completa, mas espero que próxima. Isso está muito próximo dos comentários de Luca acima. Acredito que a resposta é que pelo menos existem constantes B ∈ℕ, a > 0 e 0 < s <1, de modo que Gap-3SAT s seja NP-completo, mesmo para uma fórmula 3CNF que é par B e é composta por: pelo menos cláusulas, para qualquer constante ϵ .uman2-ϵϵ

A prova é a seguinte. Considere um GAP-3SAT s exemplo φ em N variáveis em que cada variável aparece no máximo 5 vezes. Isso é NP-completo, como você diz na pergunta.sϕN

Agora criamos uma nova instância seguinte maneira:Φ

  1. Para cada variável em ϕ , Φ tem n variáveis y i j .xEuϕΦnyEuj
  2. Para cada conjunto de índices , um e b com um b , Φ tem um par de cláusulas y i uma¬ y i b¬ yEuumabumabΦ , e y i b ¬ y i uma ¬ y i uma . Vou me referir a elas como cláusulas de comparação, pois elas garantem que y i a = y i b se estão satisfeitas.yEuumayEubyEubyEubyEuumayEuumayEuuma=yEub
  3. Para cada cláusula em atuando nas variáveis x i , x j e x k , para cada a e b , Φ contém uma cláusula equivalente, em que x i é substituído por y i a , x j é substituído por y j b e x k é substituído por y k ( a + b ) (aqui a adição é feita no módulo n ). Vou me referir a eles como cláusulas herdadas.ϕxEuxjxkumabΦxEuyEuumaxjyjbxkyk(a+b)n

O número total de variáveis é então . Nota Φ possui 2 N n 2 cláusulas de comparação e 5m=nNΦ2Nn2cláusulas herdadas, num total de1153Nn2cláusulas. Tomandon=Nk, temosm=Nk+1e o número total de cláusulasC=11113Nn2n=Nkm=Nk+1 . Tomamosk=ϵ-1-1, entãoCm2-ϵ.C=113N2k+1=113m21k+1k=ϵ11Cm2ϵ

Em seguida, é limitado por pares 8 (máximo de 2 das cláusulas de comparação e 6 das cláusulas herdadas).Φ

Finalmente, se é insatisfatório, pelo menos ( 1 - s ) cláusulas N são insatisfeitas. Agora, se y i umy i b para qualquer um , bϕ(1s)Nyiayiba,b , em seguida, pelo menos cláusulas estão insatisfeitos. Observe que, para satisfazer as cláusulas ( 1 - s ) N insatisfeitas em um conjunto de cláusulas herdadas para a , b fixo , a atribuição das variáveis y : a , y :n1(1s)Na,by:a e y : ( a + b ) devem diferir pelo menos 1 - sy:by:(a+b)posições, deixando pelo menos1-s1s5Ncomparação de cláusulas insatisfatórias. Isso deve valer para todas as opções deaeb, portanto, pelo menos1-s1s5N(n1)abcláusulas de comparação Cdevem permanecer insatisfeitas no total para que cláusulas herdadas suficientes sejam atendidas. Se, no entanto, você olhar para o outro extremo em que todas as cláusulas de comparação são satisfeitas, então ( 1 - s ) N n 2 = ( 1 - s ) m 2 k + 11s5Nn2=3(1s)11CcláusulasCsão insatisfatórias. Portanto, permanece um hiato (embora reduzido) coms=4+s(1s)Nn2=(1s)m2k+1k+1=(1s)C .s=4+s5

As constantes provavelmente precisam ser verificadas duas vezes.

Joe Fitzsimons
fonte
Obrigado Joe. Desculpe se isso não estava claro, mas nesta questão, eu exijo que as três variáveis ​​em cada cláusula sejam todas distintas e, portanto, as cláusulas de comparação conforme elas são gravadas não podem ser usadas. Eu tenho uma prova do mesmo fato (cláusulas de pareamento limitado, Ω (n ^ (2 − ε)), com gap) que usa gráficos de expansor, mas se pode ser provado sem o uso de expansores, estou muito interessado.
Tsuyoshi Ito
@ Tsuyoshi: Ah, entendo. Na verdade, inicialmente eu havia provado isso para mim com variáveis ​​distintas, então há uma maneira muito fácil de obtê-lo da forma que você deseja. Você simplesmente atribui as cláusulas de comparação de uma maneira ligeiramente diferente. Em vez das duas cláusulas Eu dei o que você precisa 4: , y i um¬ y i byiayibyi(a+b) , ¬ y i umyiayibyi(a+b) e ¬ um + b ) . Claramente, eles reduzem as mesmas 2 cláusulas variáveis ​​de antes. Obviamente, isso distorce as constantes, mas não faz outra diferença. yiayibyi(a+b)yiayibyi(a+b)
Joe Fitzsimons
Talvez haja uma maneira de contornar o fator usando kϵ , embora a implementação mais ingênua disso dê exemplos que crescem muito ligeiramente mais rápido que o polinômio. k=k(n)
Joe Fitzsimons
Verificarei os detalhes com mais cuidado mais tarde, mas a idéia de usar a, b e (a + b) parece funcionar. Isso deve me libertar de lidar explicitamente com os expansores. Obrigado!
Tsuyoshi Ito
Sem problemas. Ainda bem que pude ajudar.
Joe Fitzsimons