# 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$_1$,...,i$_q$ e uma função booleana f$_R$: {0,1}$^q$->{0,1} e aceita se e somente se f$_R$(π(i$_1$,...,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$_1$,...,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$_2$ ∨ x$_{10}$ ∨ x$_{11}$ ∨ x$_{12}$ = ( x$_2$ ∨ x$_{10}$ ∨ y$_R$) ∧ ( ${\bar {y_{R}}}$ ∨ x$_{11}$ ∨ x$_{12}$). 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$_1$,...,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.