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 Fsuch 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.
Satisfiability problem 3-SAT problem NP-complete problem One-In-Three 3-SAT problem Molecular Solution DNA-based Supercomputing
Nung-Yue Shi Chih-Ping Chu
Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan City 701, Taiwan, Republic of China
国际会议
2009 WASE International Conference on Information Engineering(2009年国际信息工程会议)(ICIE 2009)
太原
英文
620-625
2009-07-10（万方平台首次上网日期，不代表论文的发表时间）