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 1 ∨ x 2 ∨ x 4 ) ∧ (¬ x 1 ∨¬ x 3 ∨ x 4 ) ∧ ( x 1 ∨ x 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
fonte
Respostas:
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 ϵ .an2−ϵ ϵ
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:Φ
O número total de variáveis é então . Nota Φ possui 2 N n 2 cláusulas de comparação e 5m=nN Φ 2Nn2 cláusulas herdadas, num total de1153Nn2 cláusulas. Tomandon=Nk, temosm=Nk+1e o número total de cláusulasC=11113Nn2 n=Nk m=Nk+1 . Tomamosk=ϵ-1-1, entãoC∝m2-ϵ.C=113N2k+1=113m2−1k+1 k=ϵ−1−1 C∝m2−ϵ
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 um ≠ y i b para qualquer um , bϕ (1−s)N yia≠yib a,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 :n−1 (1−s)N a,b y:a e y : ( a + b ) devem diferir pelo menos 1 - sy:b y:(a+b) posições, deixando pelo menos1-s1−s5N comparação de cláusulas insatisfatórias. Isso deve valer para todas as opções deaeb, portanto, pelo menos≈1-s1−s5N(n−1) a b clá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 + 1≈1−s5Nn2=3(1−s)11C cláusulasCsão insatisfatórias. Portanto, permanece um hiato (embora reduzido) coms′=4+s(1−s)Nn2=(1−s)m2k+1k+1=(1−s)C .s′=4+s5
As constantes provavelmente precisam ser verificadas duas vezes.
fonte