3SAT um em três

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em Teoria da complexidade, o problema 3SAT um-em-três (também conhecido como SAT 1-em-3 e3SAT exatamente-1) é um problema NP-completo. O problema é uma variante do problema da 3-satisfabilidade (3SAT). Como no 3SAT, o input é uma coleção de cláusulas, onde cada cláusula consiste exatamente de três literais, e cada literal ou é uma variável ou é sua negação. O problem a 3SAT um-em-três é determinar se existe uma valoração para as variáveis de modo que cada cláusula tenha exatamente um literal verdadeiro (e, consequentemente, exatamente dois literais falsos). (Em contraste, o problema 3SAT comum exige que toda cláusula tenha pelo menos um literal verdadeiro.)

O 3SAT um-em-três é listado como o problema NP-completo LO4 na referência padrão, Computers and Intractability: A Guide to the Theory of NP-Completeness por Michael R. Garey e David Stifler Johnson. Thomas J. Schaefer provou que ele é NP-completo através de um caso especial do Teorema da dicotomia de Schaefer, que afirma que qualquer problema que generaliza de algum modo a Problema de satisfatibilidade booleana ou está na classe P ou é NP-completo. 1

Schaefer nos fornece uma construção que permite fazer uma simples Redução em tempo polinomial do 3SAT para o 3SAT um-em-três. Seja"(x ouy ouz)" uma cláusula numa fórmula 3FNC. Adicione seis novas variáveis booleanas a, b, c, d, e, ef, que serão usadas para simular somente essa cláusula e nenhuma outra. Seja R(u,v,w) um predicado que é verdadeiros se e somente se exatamente um se somente um dos booleanos u, v, and w é verdadeiro. Então a fórmula "R(x,a,d) e R(y,b,d) e R(a,b,e) e R(c,d,f) e R(z,c,falso)" é satisfatível por algum arranjo das novas variáveis se e somente se pelo menos um x, y, ou z é verdadeiro. Nós podemos então converter qualquer instância de 3SAT com m cláusulas e n variáveis numa instância de 3SAT com 5 cláusulas m e n + 6m variáveis.

Outra redução envolve somente quatro novas variáveis e três cláusulas: R(\neg x, a, b) \land R(b, y, c) \land R(c, d, \neg z).

Para provar que R deve existir, primeiro deve-se exprimir R como um produto de maxitermos, e então mostrar que

x\lor y \lor z = (\neg x\lor a\lor b)\land(\neg y\lor c\lor d)\land(\neg z\lor e\lor f)\land(a\lor c\lor e)

Note que o lado esquerdo é avaliado como verdade se e somente se o lado direito é satisfeito por um 3SAT um-em-três. As outras variáveis são variáveis novas que não existem em nenhuma expressão.

The one-in-three 3SAT problem is often used in the literature as a known NP-complete problem in a reduction to show that other problems are NP-complete.

Algoritmos[editar | editar código-fonte]

Como esse problema é equivalente ao problema de satisfação de restrições com restrições binárias e no máximo 3 valores para cada variável, algoritmos para PSRs podem ser aplicados. Se n é o número de cláusulas, então ele pode ser resolvido em tempo O(1.3644^n) .2

Variações[editar | editar código-fonte]

No problema 3SAT um em três monótono,cada literal é simplesmente uma variável; em outras palavras, não existe negação. Este problema também é NP-completo, como provado por Schaefer.1 De fato, esse era o problema original do ponto de vista de Schaefer, que ele chamou de SATISABILIDADE UM-EM-TRÊS.

Nós podemos pensar em uma instância do SAT um-em-três como um grafo, com um vértice para cada variável e cada cláusula, e uma aresta conectando uma variável a uma cláusula se ela ocorre (positivamente ou negativamente) naquela cláusula. No 3SAT um-em-três planar, é assumido que esse grafo seja um grafo planar. Este problema também é NP-completo.3

Referências[editar | editar código-fonte]

  1. a b Schaefer, Thomas J. (1978). "The complexity of satisfiability problems". Proceedings of the 10th Annual ACM Symposium on Theory of Computing: 216–226. DOI:10.1145/800133.804350. 
  2. (2005) "3-coloring in time O(1.3289n)". Journal of Algorithms 54 (2): 168–204. DOI:10.1016/j.jalgor.2004.06.008.
  3. Laroche, Philippe (1993). "Planar 1-in-3 satisfiability is NP-complete". Comptes rendus de l'Académie des sciences. Série 1, Mathématique ISSN 0764-4442: vol. 316, no4, pp. 389-392.