Redução de 3-SAT para Subconjunto Independente em Grafos: Implicações e Perspectivas
Resumo
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.
Referências
Braich, R. S., Chelyapov, N., Johnson, C. R., Rothemund, P., and Adleman, L. (2002). Solution of a 20-variable 3-sat problem on a dna computer. Science, 296:499 – 502.
Cané, M., Coll, J., Rojo, M., and Villaret, M. (2023). Sat-it: the interactive sat tracer. In Artificial Intelligence Research and Development, pages 337–346. IOS Press.
Chellali, M., Favaron, O., Haynes, T., Hedetniemi, S., and McRae, A. A. (2014). Independent [1, k]-sets in graphs. Australas. J Comb., 59:144–156.
Choi, V. (2011). Quantum information & computation. 11(7-8):638–648.
Committee, I. S. et al. (1990). Ieee standard glossary of software engineering terminology. IEEE Std, 610:12.
Cook, S. A. (2021). The complexity of theorem-proving procedures (1971).
Fallah, F., Devadas, S., and Keutzer, K. (1998). Functional vector generation for hdl models using linear programming and 3-satisfiability. In Proceedings 1998 Design and Automation Conference. 35th DAC. (Cat. No.98CH36175), pages 528–533.
Garey, M. R. and Johnson, D. S. (1979). Computers and intractability, volume 174. freeman San Francisco.
Gibney, D., Hoppenworth, G., and Thankachan, S. V. (2020). Simple reductions from formula-sat to pattern matching on labeled graphs and subtree isomorphism. pages 232–242.
Hopfield, J. and Tank, D. (1989). Neural architecture and biophysics for sequence recognition. In Neural models of plasticity, pages 363–377. Elsevier.
Iwata, Y. and Yoshida, Y. (2015). On the equivalence among problems of bounded width. pages 754–765.
Karve, V. and Hirani, A. N. (2021). Graphsat - a decision problem connecting satisfiability and graph theory. ArXiv, abs/2105.11390.
Kusper, G., Biró, C., and Balla, T. (2020). Investigation of the efficiency of conversion of directed graphs to 3-sat problems. 2020 IEEE 14th International Symposium on Applied Computational Intelligence and Informatics (SACI), pages 000227–000234.
Lintzmayer, C. N. and Mota, G. O. (2020). Análise de algoritmos e estruturas de dados. Centro de Matemática, Computação e Cognição.
Lipton, R. J. (1995). Dna solution of hard computational problems. science, 268(5210):542–545.
Lucchesi, C. L. (1979). Aspectos teóricos da computação, volume 8. Instituto de Matemática Pura e Aplicada, CNPq.
Mansor, M. A. and Sathasivam, S. (2016). Accelerating activation function for 3-satisfiability logic programming. International Journal of Intelligent Systems and Applications, 8(10):44.
Mansor, M. A., Sathasivam, S., and Kasihmuddin, M. S. M. (2018). 3-satisfiability logic programming approach for cardiovascular diseases diagnosis. In AIP Conference Proceedings, volume 1974. AIP Publishing.
Marchetti, K. and Bodily, P. (2022). Visualizing the 3sat to clique reduction process. 2022 Intermountain Engineering, Technology and Computing (IETC), pages 1–5.
Moreira, N. (2016). Classes de complexidade.
Pan, H.-Y. and Chu, Z.-F. (2023). A semi-tensor product based all solutions boolean satisfiability solver. Journal of Computer Science and Technology, 38(3):702–713.
Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley, Reading, Massachusetts.
Papadimitriou, C. H. (2003). Computational complexity. In Encyclopedia of computer science, pages 260–265.
Papadimitriou, C. H. and Steiglitz, K. (2013). Combinatorial optimization: algorithms and complexity. Courier Corporation.
Rocha, T. A. (2014). Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes p e np conp através de lógicas com quantificadores de segunda ordem.
Saxena, D., Duro, J. A., Tiwari, A., Deb, K., and Zhang, Q. (2013). Objective reduction in many-objective optimization: Linear and nonlinear algorithms. IEEE Transactions on Evolutionary Computation, 17:77–99.
Sinha, A., Saxena, D., Deb, K., and Tiwari, A. (2013). Using objective reduction and interactive procedure to handle many-objective optimization problems. Appl. Soft Comput., 13:415–427.
Sipser, M. (1996). Introduction to the theory of computation. ACM Sigact News, 27(1):27–29.
Tovey, C. A. (2002). Tutorial on computational complexity. Interfaces, 32(3):30–61.
Zhang, Z., Paredes, R., Sundar, B., Quiroga, D., Kyrillidis, A., Duenas-Osorio, L., Pagano, G., and Hazzard, K. R. (2024). Grover-qaoa for 3-sat: Quadratic speedup, fair-sampling, and parameter clustering. arXiv preprint arXiv:2402.02585.
Cané, M., Coll, J., Rojo, M., and Villaret, M. (2023). Sat-it: the interactive sat tracer. In Artificial Intelligence Research and Development, pages 337–346. IOS Press.
Chellali, M., Favaron, O., Haynes, T., Hedetniemi, S., and McRae, A. A. (2014). Independent [1, k]-sets in graphs. Australas. J Comb., 59:144–156.
Choi, V. (2011). Quantum information & computation. 11(7-8):638–648.
Committee, I. S. et al. (1990). Ieee standard glossary of software engineering terminology. IEEE Std, 610:12.
Cook, S. A. (2021). The complexity of theorem-proving procedures (1971).
Fallah, F., Devadas, S., and Keutzer, K. (1998). Functional vector generation for hdl models using linear programming and 3-satisfiability. In Proceedings 1998 Design and Automation Conference. 35th DAC. (Cat. No.98CH36175), pages 528–533.
Garey, M. R. and Johnson, D. S. (1979). Computers and intractability, volume 174. freeman San Francisco.
Gibney, D., Hoppenworth, G., and Thankachan, S. V. (2020). Simple reductions from formula-sat to pattern matching on labeled graphs and subtree isomorphism. pages 232–242.
Hopfield, J. and Tank, D. (1989). Neural architecture and biophysics for sequence recognition. In Neural models of plasticity, pages 363–377. Elsevier.
Iwata, Y. and Yoshida, Y. (2015). On the equivalence among problems of bounded width. pages 754–765.
Karve, V. and Hirani, A. N. (2021). Graphsat - a decision problem connecting satisfiability and graph theory. ArXiv, abs/2105.11390.
Kusper, G., Biró, C., and Balla, T. (2020). Investigation of the efficiency of conversion of directed graphs to 3-sat problems. 2020 IEEE 14th International Symposium on Applied Computational Intelligence and Informatics (SACI), pages 000227–000234.
Lintzmayer, C. N. and Mota, G. O. (2020). Análise de algoritmos e estruturas de dados. Centro de Matemática, Computação e Cognição.
Lipton, R. J. (1995). Dna solution of hard computational problems. science, 268(5210):542–545.
Lucchesi, C. L. (1979). Aspectos teóricos da computação, volume 8. Instituto de Matemática Pura e Aplicada, CNPq.
Mansor, M. A. and Sathasivam, S. (2016). Accelerating activation function for 3-satisfiability logic programming. International Journal of Intelligent Systems and Applications, 8(10):44.
Mansor, M. A., Sathasivam, S., and Kasihmuddin, M. S. M. (2018). 3-satisfiability logic programming approach for cardiovascular diseases diagnosis. In AIP Conference Proceedings, volume 1974. AIP Publishing.
Marchetti, K. and Bodily, P. (2022). Visualizing the 3sat to clique reduction process. 2022 Intermountain Engineering, Technology and Computing (IETC), pages 1–5.
Moreira, N. (2016). Classes de complexidade.
Pan, H.-Y. and Chu, Z.-F. (2023). A semi-tensor product based all solutions boolean satisfiability solver. Journal of Computer Science and Technology, 38(3):702–713.
Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley, Reading, Massachusetts.
Papadimitriou, C. H. (2003). Computational complexity. In Encyclopedia of computer science, pages 260–265.
Papadimitriou, C. H. and Steiglitz, K. (2013). Combinatorial optimization: algorithms and complexity. Courier Corporation.
Rocha, T. A. (2014). Complexidade descritiva de classes de complexidade probabilísticas de tempo polinomial e das classes p e np conp através de lógicas com quantificadores de segunda ordem.
Saxena, D., Duro, J. A., Tiwari, A., Deb, K., and Zhang, Q. (2013). Objective reduction in many-objective optimization: Linear and nonlinear algorithms. IEEE Transactions on Evolutionary Computation, 17:77–99.
Sinha, A., Saxena, D., Deb, K., and Tiwari, A. (2013). Using objective reduction and interactive procedure to handle many-objective optimization problems. Appl. Soft Comput., 13:415–427.
Sipser, M. (1996). Introduction to the theory of computation. ACM Sigact News, 27(1):27–29.
Tovey, C. A. (2002). Tutorial on computational complexity. Interfaces, 32(3):30–61.
Zhang, Z., Paredes, R., Sundar, B., Quiroga, D., Kyrillidis, A., Duenas-Osorio, L., Pagano, G., and Hazzard, K. R. (2024). Grover-qaoa for 3-sat: Quadratic speedup, fair-sampling, and parameter clustering. arXiv preprint arXiv:2402.02585.
Publicado
11/09/2024
Como Citar
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.
Redução de 3-SAT para Subconjunto Independente em Grafos: Implicações e Perspectivas. In: ESCOLA REGIONAL DE COMPUTAÇÃO DO CEARÁ, MARANHÃO E PIAUÍ (ERCEMAPI), 12. , 2024, Parnaíba/PI.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 189-198.
DOI: https://doi.org/10.5753/ercemapi.2024.243754.
