Problema da satisfatibilidade de circuito

Predefinição:Formatar referências Na teoria da ciência da computação, o problema da satisfatibilidade de circuito (também conhecido como CIRCUITO-SAT, CircuitoSAT, CSAT, etc.) é o problema de decisão de determinar se um dado circuito Booleano tem uma atribuição das entradas, que torna a saída verdadeira.

Propriedades

CircuitoSAT foi provado ser NP-completo. Na verdade, é um protótipo de problema NP-completo; o Teorema de Cook-Levin é, por vezes, provado em CircuitoSAT em vez de ser provado pelas expressões Booleanas para SAT  e, em seguida, reduzido para outros problemas de satisfatibilidade para provar a sua NP-completude.

A satisfatibilidade de um circuito contendo m portas binárias arbitrárias, pode ser decidido em tempo $O(2^{0.4058m})$.

A transformação de Tseitin 

Existe uma simples redução de CircuitoSAT a SAT, conhecida como a transformação de Tseitin. A transformação é especialmente fácil de descrever, se o circuito é totalmente construído a partir de 2 entradas de portas NAND (um conjunto funcionalmente-completo de operadores Booleanos): atribuir a cada rede no circuito de uma variável e, em seguida, para cada porta NAND, construir as cláusulas na forma normal conjuntiva  (v₁ ∨ v₃) ∧ (v₂ ∨ v₃) ∧ (v₁ ∨ v₂ ∨ v₃) onde v₁ e v₂ são as entradas para a porta NAND e v₃ é a saída. Estas cláusulas descrevem completamente a relação entre as três variáveis. Unindo as cláusulas de todas as portas com uma cláusula adicional restritiva da variável de saída do circuito para ser verdade completa a redução; uma atribuição de variáveis que satisfaça as restrições existe se, e somente se, o circuito original é satisfatível, e qualquer solução é uma solução para o problema original de encontrar entradas que fazem o circuito de saída 1. (O inverso, que SAT é redutível a CircuitoSAT, é ainda mais fácil—simplesmente reescrevemos a fórmula Booleana como um circuito e o resolvemos.)