ISSN : 2319-7323

INTERNATIONAL JOURNAL OF COMPUTER SCIENCE ENGINEERING

ABSTRACT

Title	:	A Heuristic Approach for Solving the Cubic Monotone 1-in-3 SAT Problem
Authors	:	O.Kettani
Keywords	:	X3SAT, Cubic Monotone 1-in-3 SAT Problem, NP-complete, dynamic programming, heuristic
Issue Date	:	Jul-Aug 2020
Abstract	:	The present paper proposes a heuristic approach to solve a variant of the satisfiability problem (SAT) , namely the exact 3-satisfiability problem (X3SAT) which is known to remains NP-complete when restricted to expressions where every variable has exactly three occurrences, even in the absence of negated variables (Cubic Monotone 1-in-3 SAT Problem ). Firstly, this problem is converted into an equivalent system of linear equations over binary variables, then it is solved using a dynamic programming heuristic based on Das algorithm requiring O(n4) time, for input formulas over n variables. Finally, a Matlab code implementation is provided.
Page(s)	:	250-258
ISSN	:	2319-7323
Source	:	Vol. 9, No. 4