| DNA computing is an emerging new study area. In 1994, Adleman described his pioneering research on DNA computing in Science, where he computed an instance of the Hamiltonian path problem with DNA in test tubes. This is the first experimental report on DNA computing study. The main features of DNA computing are massively parallel computing ability and potential enormous data storage capacity comparing with conventional electronic computers, DNA molecules provide conceptually a revolution in computing, and more and more implications have been found in various disciplines. The four-color problem was first formulated in 1852 and was not proven until 1976. Along with other problems such as Fermat's Last Theorem, this conjecture was considered one of the great open problems in mathematics. In 1976, Haken and Appel gave the first proof, which later was improved by Robertson. First, they show every planar triangulation contains one of the configurations in their unavoidable set. Second, they show that each configuration is reducible. The second step is the part of the proof that requires the aid of a computer. Approximately 1200 hours of CPU time were required to complete the second step of the proof. In this paper, we try to solve the proof of configuration reducibility using DNA computing. Because of the massively parallel computing ability of DNA computing, we can shorten the time of the proof greatly. There is no such research up to now. First, we introduce the proof of four-color theorem in brief. Second, we introduce the property of tri-coloring to smooth triangulation and the DNA algorithm of tri-coloring. Finally, we analyze the relationship between the coloring and the signed matching, and then provide the DNA algorithm to the proof of configuration reducibility. The coding in this paper is simple and direct; the algorithm is easy to carry out. The algorithm is parallel to some extent, and it can shorten the time to prove the configuration reducibility greatly.
|
PDF Full Text Request