Skip to main content

Research Papers

An Improved Parallel DNA Algorithm of 3-SAT

Authors
  • Wei Liu
  • Shou Xia Sun
  • Ying Guo

Abstract

There are many large-size and difficult computational problems in mathematics and computer science. For many of these problems, traditional computers cannot handle the mass of data in acceptable timeframes, which we call an NP problem. DNA computing is a means of solving a class of intractable computational problems in which the computing time grows exponentially with problem size. This paper proposes a parallel algorithm model for the universal 3-SAT problem based on the Adleman-Lipton model and applies biological operations to handling the mass of data in solution space. In this manner, we can control the run time of the algorithm to be finite and approximately constant.
Year: 2007
Volume 6
Page/Article: S566-S570
DOI: 10.2481/dsj.6.S566
Published on Sep 20, 2007
Peer Reviewed