A DNA-Based Algorithm for the Solution of One-in-Three 3-SAT Problem

Satisfiability problem is given a Boolean formula, and decide if a satisfying truth assignment exists.K-SAT means that each clause has exactly k literals. One in three (1IN3) 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 in C has exactly one true literal? In this paper, we will use molecular solution to find all true assignment (3 SAT problem) and find one-in-three (1IN3) solutions on DNA based supercomputing. The complexity of the presented DNA based solution is discussed in section three. And the simulated experiment is applied to verify correction of the proposed DNA based algorithm for solving the one in three 3 SAT problem in section four.