Abstract

This paper presents a proof demonstrating that the Cubic Monotone 1-in-3 SAT Problem, which is a variant of the Boolean Satisfiability Problem (SAT), can be solved in polynomial time. The proof focuses on establishing that this problem is polynomial time reducible to the Maximum Independent Set Problem in a bounded treewidth graph. While further verification is required to validate the correctness of the proof, this claim represents a potential breakthrough in one of the most significant open problems in computer science and mathematics. 

Keywords

Bounded treewidth graph, Cubic Monotone 1-in-3 SAT Problem, Independence number, Polynomial Time Algorithm, P=NP.

References

[1] Stephen A. Cook, The Complexity of Theorem-Proving Procedures, pp. 1-8, 1971.
[Google Scholar] [Publisher Link]

[2] Richard M. Karp, Reducibility among Combinatorial Problems, University of California, 1972.
[Google Scholar] [Publisher Link]

[3] C. Moore, and J.M. Robson, “Hard Tiling Problems with Simple Tiles,” Discrete & Computational Geometry, vol. 26, pp. 573-590, 2001.
[CrossRef] [Google Scholar] [Publisher Link]

[4] A. Leonid Levin, “Universal Search Problems,” Problems of Information Transmission, vol. 9, no. 3, pp. 265-266, 1973.
[Google Scholar]

[5] Armin Biere, Hans van Maaren, and Toby Walsh, Handbook of Satisfiability, IOS Press, pp. 1-980, 2009.
[Google Scholar] [Publisher Link]

[6] Omar Kettani, “Solving the Cubic Monotone 1-in-3 SAT Problem in Polynomial Time,” Global Journal of Computer Science and Technology, vol. 23, no. A1, pp. 1-10, 2024.
[Publisher Link]

[7] Hans Leo Bodlaender, A Tourist Guide through Treewidth, Department of Computer Science, Utrecht University, pp. 1-24, 1992.
[Google Scholar] [Publisher Link]

[8] Thomas H. Cormen et al., Introduction to Algorithms, 3^rd ed., MIT Press, pp. 1-1292, 2009.
[Google Scholar] [Publisher Link]

[9] Vincent Bouchitté, and Ioan Todinca, “Treewidth and Minimum Fill-in: Grouping the Minimal Separators,” SIAM Journal on Computing, vol. 31, no. 1, pp. 212-232, 2001.
[CrossRef] [Google Scholar] [Publisher Link]

[10] Martin Davis, George Logemann, and Donald Loveland, “A Machine Program for Theorem-Proving,” Communications of the ACM, vol. 5, no. 7, pp. 394-397, 1962.
[CrossRef] [Google Scholar] [Publisher Link]

[11] J.P. Marques-Silva, and K.A. Sakallah, “GRASP: A Search Algorithm for Propositional Satisfiability,” IEEE Transactions on Computers, vol. 48, no. 5, pp. 506-521, 1999.
[CrossRef] [Google Scholar] [Publisher Link]

[12]  Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan, “A Linear-time Algorithm for Testing the truth of Certain Quantified Boolean Formulas,” Information Processing Letters, vol. 8, no. 3, pp. 121-123, 1979. [CrossRef] [Google Scholar] [Publisher Link]

[13]  R. Dechter, Bucket Elimination: A Unifying Framework for Probabilistic Inference, Learning in Graphical Models, Springer, pp. 75-104, 1998.
[CrossRef] [Google Scholar] [Publisher Link]

[14] Clark Barrett, and Cesare Tinelli, Satisfiability Modulo Theories, Handbook of Model Checking, pp. 305-343,

        2018.
        [CrossRef] [Google Scholar] [Publisher Link]