DNA Computing Of NP Complete Problem In Discrete Mathematics

DNA computing has been a touchy point for research in mathematics, biology, chemisty, and computer science from 1994 to present days. It has solved many problems such as NP complete problem.One of many difficulties and main technology that DNA computing faces is how to reduce the large coding quantity, namely, to slove"index explosion"problem. As a result, we should improve the existing computing methods or find out new computing ways. At present, DNA computing is demenstrated relatively muturely in computing theory feasibility and is still exploring surface technology.As the surface thnology comes to mature, DNA computing surely tends to transfer from laborotary to market.Discrete mathematics consists of so many NP complete problems. They are principal normal form problem, graph coloring problem, transitive closure problem, maximum matching problem, and travel quotient. Nowadays, DNA computing is the most effetive method for solving NP complete problems. This paper solves three typical problems in discrete mathematics by means of DNA computing. They are principal normal form problem in propositional logic, graph coloring problem in graph theory, and transitive closure problem in set theory.This article introduces the background of DNA computering, current situation, principle and basic model at first. And then, it solves three corresponding problems. Firstly, as typical advantage of DNA hairpin structure is that we do not need special biological operation, we can reduce biological reaction time at a great degree. And according to the definition of principal normal form and DNA hairpin structure, we can solve principal normal form of propositional formula in decrete mathematics by means of DNA hairpin structure model. Secondly, by means of DNA computer model, adopting reasonable coding to produce solution space based on ternary notion, and by gradually using the method that meets the definition of DNA chain, we can reduce amount of the DNA molecule chains from O( 3 n)to O( 2 n)in graph 3 coloring problem. This way can wonderfully solve"index explosion"problem in graph 3 coloring problem and make it into application. Thirdly, by make using of Adleman's test tube model, consulting Hamilton's routing problem theory, this paper solves transitive closure problem that is hard to deal with. To sum up, the paper talks about the close relation between DNA computing and mathematics as well as its application in mathematics field; it also discusses its further research direction.