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.