A DNA-based Algorithm for the Solution of Not-All-Equal 3-SAT Problem
Satisfiability problem is given a Boolean formula, and decide if a satisfying truth assignment exists.((-X12)VX5)^ ((-X24)VX3V(- X13)VX9)^…^(X12)^(X17VX8(0X18)) is an example of Boolean formula. k-SAT means that each clause has exactly k literals. Not-All-Equal (NAE) 3-SAT problem is defined by Garey and Johnson in 1979 as follows: There is a set V of variables and a collection C of clauses over V such that each clause has 3 literals. And the question is : Is there a truth assignment for V such that each clause has at least one true and at least one false literal?Note that the only difference with 3-SAT is that as well as one true literal, there must also be one false literal in each clause.In this paper, we will use molecular solution to find all true assignment (3 SAT problem) and furthermore find Not-All-Equal (NAE) solutions on DNA-based Supercomputing. Finally, the simulated experiment is applied to verify correction of the proposed DNA-based algorithm for solving the Not-All-Equal 3-SAT problem.
Satisfiability problem 3-SAT problem NP-complete problem Not-All-Equal 3-SAT problem Molecular Solution DNA-based Supercomputing
Nung-Yue Shi Chih-Ping Chu
Department of Computer Science and Information Engineering, National Cheng Rung University, Tainan City 701, Taiwan, Republic of China
国际会议
2009 WASE International Conference on Information Engineering(2009年国际信息工程会议)(ICIE 2009)
太原
英文
753-758
2009-07-10（万方平台首次上网日期，不代表论文的发表时间）