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
[editar | editar código-fonte]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)
[editar | editar código-fonte]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 Ri ∈ V, obtemos poly(x) strings desde que o tamanho de cada string r(x) = O(log |x|).
- Para cada Ri
- V escolhe q posições i1,...,iq e uma função booleana fR: {0,1}q->{0,1} e aceita se e somente se fR(π(i1,...,iq)). 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 x1,...,xl, 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 fR(xi1,...,xiq) usando 2q cláusulas SAT. Cláusulas de tamanho q são convertidas para tamanho 3 adicionando uma nova variável (auxiliar) e.g. x2 ∨ x10 ∨ x11 ∨ x12 = ( x2 ∨ x10 ∨ yR) ∧ ( ∨ x11 ∨ x12). Isto requer no máximo de q2q cláusulas 3-SAT.
- Se z ∈ L então
- existe uma prova π tal que Vπ (z) aceita para todo Ri.
- Todas as cláusulas são satisfeitas se xi = π(i) e a variável auxiliar são adicionadas corretamente.
- Se a entrada z ∉ L então
- Para cada atribuição de x1,...,xl and yR's, a prova correspondente π(i) = xi causa a rejeição do Verificador para metade de todos os R ∈ {0,1}r(|z|).
- Para cada R, uma cláusula que representa fR falha.
- Portanto a fração da cláusula falha.
- Para cada atribuição de x1,...,xl and yR's, a prova correspondente π(i) = xi causa a rejeição do Verificador para metade de todos os R ∈ {0,1}r(|z|).
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
[editar | editar código-fonte]Hosted [1] 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 ir, jr, kr na prova π e um bit br. E aceita se somente se
π(ir) ⊕ π(jr) ⊕ π(kr) ⊕ = br.
O Verificador tem completude(1-ε) e solidez 1/2 + ε (referente a PCP (complexidade)). O Verificador satisfaz
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
Problemas relacionados
[editar | editar código-fonte]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[2] 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,[3][4] e todo B ≥ 3[5] (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.[5]
A melhor possibilidade para taxa de aproximação para MAX-3SAT(B), como uma função de B, é no mínimo e no máximo ,[6] a não ser que NP=RP. Alguns limites explicates das constantes de aproximação para certos valores de B são conhecidos.[7] [8] [9] 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.[10]
MAX-EkSAT é a versão parametrizada de MAX-3SAT onde cada cláusula tem exatamente literais, para k ≥ 3. E pode ser eficientemente aproximada com uma taxa de aproximação de 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.[11]
Referências
[editar | editar código-fonte]- ↑ 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 0-8218-2872-X
- ↑ 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.
- ↑ a b 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]