Satisfação booleana: algoritmos, aplicações, implementações
Palavras-chave:
SAT, Satisfação booleana, Algoritmos
Resumo
Neste artigo considera-se em detalhe o problema de satisfação booleana (SAT) e descrevem-se os algoritmos discretos completos que são normalmente utilizados para a sua solução. É mostrado que SAT tem inúmeras aplicações práticas. Portanto, o desenvolvimento e a implementação de algoritmos eficientes assumem actualmente grande importância. Finalmente, são analisadas várias realizações de algoritmos baseadas em hardware reconfigurável e é comparado o seu desempenho.