A Molecular Solution for the Ramsey Number on DNA-Based Supercomputing

Ramseys theorem is a foundational result in combinatorics, which adopts many technologies in each embranchment of mathematics. Its conclusions are very important in set theory, logic, analysis, algebra and so on. But the Ramsey number problem is one of the most difficult problems in mathematics, and there are only 9 Ramsey numbers that have been solved. The objective of this paper is to solve the Ramsey number problem. We propose an improved DNA computing model based on the biological operations in the Adleman-Lipton model, the solution space of stickers in the sticker-based model, and the add-bit-sequence coding method proposed by Xu Jin, et al. According to the proposed algorithm, we can obtain lower bound and upper bound by means of specific mathematical formulas which already exist firstly. For each number from lower bound to upper bound, we build the initial answer space. Then, we remove the DNA chains which accord with special qualifications. Finally, we detect the final test tube to confirm whether the current number is a Ramsey number or not. The theoretic analysis and simulated experiments show that the solution to the difficult Ramsey number problem is possible in acceptable time, provided that the technology of DNA biology is mature enough in the future.