Redução de 3-SAT para Subconjunto Independente em Grafos: Implicações e Perspectivas - Santana, Vitor José Ferreira dos S. de; Moura, Ericksulino M. de A.; Pereira, José Miqueias de A.; Carvalho, Juliana Oliveira de; Gonçalves, Glauber Dias (Anais da Escola Regional de Computação do Ceará, Maranhão e Piauí (ERCEMAPI), 2024)
Este estudo investiga a redução do problema 3-SAT para Subconjunto Independente em grafos, preservando a complexidade NP-completa dos problemas originais. A metodologia utiliza a estrutura matemática do 3-SAT para traduzir cláusulas booleanas em relações gráficas, viabilizando a verificação de conjuntos independentes. Os resultados mostram que esta abordagem pode oferecer soluções eficientes e escaláveis, úteis em verificações de consistência em sistemas especialistas, otimização de circuitos digitais e outros desafios computacionais complexos.