MAX-3SAT

MAX-3SAT é um problema em complexidade computacional, uma subárea da ciência da computação. Este problema generaliza o problema da satisfatibilidade booleana (SAT), que é um problema de decisão dentro da teoria da complexidade. E é definido como:

Dada uma 3-CNF formula Φ (i.e. com no máximo 3 variáveis por cláusula), ache uma atribuição que satisfaz o maior número de cláusulas.

MAX-3SAT é um problema canônico completo da classe de complexidade MAXSNP (ver Papadimitriou pg. 314).

Aproximação

A versão de decisião de MAX-3SAT é NP-completa. No entanto, uma solução em tempo polinomial somente pode ser alcançada se P = NP. Uma aproximação por um fator de 2 pode ser alcançada com esse simples algoritmo:

• Coloque como saída a solução em que a maioria das cláusulas sejam satisfeitas, tanto quando todas as variáveis forem verdadeiras ou todas as variáveis fores falsas.
• Cada cláusula é satisfeita por uma das duas soluções, portanto, uma solução satisfaz, pelo menos, metade das cláusulas.

O algoritmo de Karloff-Zwick roda em tempo polinomial e satisfaz ≥ 7/8 das cláusulas.

Teorema 1 (não-aproximação)

O teorema do PCP implica que existe um ε > 0 tal que (1-ε)-aproximação de MAX-3SAT é NP-difícil.

Prova:

Pelo teorema PCP, qualquer problema NP-completo L ∈ PCP(O(log (n)), O(1)). Para x ∈ L, uma fórmula 3-CNF Ψ_x é construída tal que:

• x ∈ L ⇒ Ψ_x é satisfatível
• x ∉ L ⇒ não mais que (1-ε)m cláusulas de Ψ_x são satisfatíveis.

O verificador V lê todos os bits de uma vez i.e. faz consultas não-adaptativas. Isto é valido, pois o número de consultas permanece constante.

• Considere q como sendo o número de consultas.
• Enumerando randomicamente todas as strings R_i ∈ V, obtemos poly(x) strings desde que o tamanho de cada string r(x) = O(log |x|).
• Para cada R_i
  • V escolhe q posições i₁,...,i_q e uma função booleana f_R: {0,1}^q->{0,1} e aceita se e somente se f_R(π(i₁,...,i_q)). Aqui π se refere a prova obtida pelo oráculo.

O próximo passo é tentar encontrar uma fórmula booleana para simular isto. Introduzimos variáveis booleanas  x₁,...,x_l, onde l é o tamanho da prova. Para demonstrar que o Verificador roda em tempo polinomial probabilístico, precisamos de uma correspondência entre o número de cláusulas satisfaríeis e a probabilidade de o Verificador aceitar.

• Para cada R, adicione cláusulas representadas por f_R(x_i1,...,x_iq) usando 2^q cláusulas SAT. Cláusulas de tamanho q são convertidas para tamanho 3 adicionando uma nova variável (auxiliar) e.g. x₂ ∨ x₁₀ ∨ x₁₁ ∨ x₁₂ = ( x₂ ∨ x₁₀ ∨ y_R) ∧ ( ${\bar {y_{R}}}$ ∨ x₁₁ ∨ x₁₂). Isto requer no máximo de q2^q cláusulas 3-SAT.
• Se z ∈ L então
  • existe uma prova π tal que V^π (z) aceita para todo R_i.
  • Todas as cláusulas são satisfeitas se x_i = π(i) e a variável auxiliar são adicionadas corretamente.
• Se a entrada z ∉ L então
  • Para cada atribuição de  x₁,...,x_l and y_R's, a prova correspondente π(i) = x_i causa a rejeição do Verificador para metade de todos os R ∈ {0,1}^r(|z|).
    • Para cada R, uma cláusula que representa f_R falha.
    • Portanto a fração ${\frac {1}{2}}{\frac {1}{q2^{q}}}$ da cláusula falha.

Pode-se concluir que, se este é válido para todos os problemas de NP-completos, então, o teorema PCP deve ser verdadeiro.

Teorema 2

Hosted  demonstra um resultado mais conciso do Teorema 1, i.e. o valor mais conhecido para ε.

Construimos um verificador PCP para 3-SAT que lê somente 3 bits da prova.

Pra cada ε > 0, existe um verificador PCP M para 3-SAT que lê uma string aleatória r de tamanho O(log(n)) e computa o resultado das posições i_r, j_r, k_r na prova π e um bit b_r. E aceita se somente se

π(i_r) ⊕ π(j_r) ⊕ π(k_r) ⊕ = b_r.

O Verificador tem completude(1-ε) e solidez 1/2 + ε (referente a PCP (complexidade)). O Verificador satisfaz

$z\in L\implies \exists \pi Pr[V^{\pi }(x)=1]\geq 1-\epsilon$

$z\not \in L\implies \forall \pi Pr[V^{\pi }(x)=1]\leq {\frac {1}{2}}+\epsilon$

Na primeira das duas equações onde temos a igualdade "=1" como costume, uma poderia encontrar a prova π resolvendo o sistema linear de equações (ver MAX-3LIN-EQN) implicando que P = NP.

• Se z ∈ L, uma fração ≥ (1- ε) de cláusulas são satisfeitas.
• Se z ∉ L, então para uma (1/2- ε) fração de R, 1/4 cláusulas são contraditas.

Isso é suficiente para provar a dificuldade da taxa de aproximação

${\frac {1-{\frac {1}{4}}({\frac {1}{2}}-\epsilon )}{1-\epsilon }}={\frac {7}{8}}+\epsilon '$

Problemas relacionados

MAX-3SAT(B) é restrito ao caso especial de MAX-3SAT onde cada variável ocorre no máximo em B cláusulas. Antes que o teorema PCP fosse provado, Papadimitriou and Yannakakis mostraram que para alguma constante fixa B, o problema é MAX SNP-difícil. Consequentemente com o teorema PCP, é também APX-difícil. Isto é útil porque MAX-3SAT(B) também pode ser usado para obter uma redução PTAS-preserving de forma que MAX-3SAT não pode. Provas de valores explícitos de B incluem: todo B ≥ 13, e todo B ≥ 3 (que é a melhor possibilidade).

Além disso, embora o problema de decisão 2SAT é solúvel em tempo polinomial, MAX-2SAT(3) também é  APX-defícil.

A melhor possibilidade para taxa de aproximação para MAX-3SAT(B), como uma função de B, é no mínimo $7/8+\Omega (1/B)$ e no máximo $7/8+O(1/{\sqrt {B}})$, a não ser que NP=RP. Alguns limites explicates das constantes de aproximação para certos valores de B são conhecidos. Berman, Karpinski e Scott provaram que as instâncias "criticas" de MAX-3SAT na qual cada literal ocorre exatamente duas vezes, e cada cláusula tem tamanho 3, o problema é aproximado-difícil para algum fator constante.

MAX-EkSAT é a versão parametrizada de MAX-3SAT onde cada cláusula tem exatamente $k$ literais, para k ≥ 3. E pode ser eficientemente aproximada com uma taxa de aproximação de $1-(1/2)^{k}$ usando ideias de teoria da codificação.

Foi provado que instâncias aleatórias de MAX-3SAT podem ser aproximadas por um fator de 9/8.

 [[Categoria:teoria da computação]]

Referências

Lecture Notes from University of California, Berkeley

Coding theory notes at University at Buffalo