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.

Referências

↑ Håstad, Johan (2001)
↑ Christos Papadimitriou and Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02–04, 1988.
↑ Rudich et al., "Computational Complexity Theory," IAS/Park City Mathematics Series, 2004 page 108 ISBN 082182872X
↑ Sanjeev Arora, "Probabilistic Checking of Proofs and Hardness of Approximation Problems," Revised version of a dissertation submitted at CS Division, U C Berkeley, in August 1994.
1 2 Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1999), Complexity and Approximation.
↑ Luca Trevisan. 2001.
↑ On some tighter inapproximability results, Piotr Berman and Marek Karpinski, Proc.
↑ P. Berman and M. Karpinski, Improved Approximation Lower Bounds on Small Occurrence Optimization, ECCC TR 03-008 (2003)
↑ P. Berman, M. Karpinski and A. D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT, ECCC TR 03-022 (2003).
↑ P. Berman, M. Karpinski and A. D. Scott, Approximation Hardness of Short Symmetric Instances of MAX-3SAT, ECCC TR 03-049 (2003).
↑ W.F.de la Vega and M.Karpinski, 9/8-Approximation Algorithm for Random MAX-3SAT, ECCC TR 02-070 (2002);RAIRO-Operations Research 41(2007),pp.95-107]

Lecture Notes from University of California, Berkeley

Coding theory notes at University at Buffalo

[1] Håstad, Johan (2001)

[2] Christos Papadimitriou and Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02–04, 1988.

[3] Rudich et al., "Computational Complexity Theory," IAS/Park City Mathematics Series, 2004 page 108 ISBN 082182872X

[4] Sanjeev Arora, "Probabilistic Checking of Proofs and Hardness of Approximation Problems," Revised version of a dissertation submitted at CS Division, U C Berkeley, in August 1994.

[acgkmsp-5] 1 2 Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1999), Complexity and Approximation.

[6] Luca Trevisan. 2001.

[7] On some tighter inapproximability results, Piotr Berman and Marek Karpinski, Proc.

[8] P. Berman and M. Karpinski, Improved Approximation Lower Bounds on Small Occurrence Optimization, ECCC TR 03-008 (2003)

[9] P. Berman, M. Karpinski and A. D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT, ECCC TR 03-022 (2003).

[10] P. Berman, M. Karpinski and A. D. Scott, Approximation Hardness of Short Symmetric Instances of MAX-3SAT, ECCC TR 03-049 (2003).

[11] W.F.de la Vega and M.Karpinski, 9/8-Approximation Algorithm for Random MAX-3SAT, ECCC TR 02-070 (2002);RAIRO-Operations Research 41(2007),pp.95-107]