Reduction of 3-SAT to Independent Set in Graphs: Implications and Perspectives
Abstract
This study investigates the reduction of the 3-SAT problem to Independent Subset in graphs, preserving the NP-complete complexity of the original problems. The methodology uses the 3-SAT mathematical structure to translate Boolean clauses into graphical relationships, enabling the verification of independent sets. The results show that this approach can offer efficient and scalable solutions, useful in consistency checks in specialized systems, optimization of digital circuits and other complex computational challenges.
References
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.
Published
2024-09-11
How to Cite
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.
Reduction of 3-SAT to Independent Set in Graphs: Implications and Perspectives. In: REGIONAL SCHOOL ON COMPUTING OF CEARÁ, MARANHÃO, AND 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.
