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.%Ramsey理论是组合数学中一个庞大而又丰富的领域,在集合论、逻辑学、分析以及代数学上具有极重要的应用.Ramsey数的求解是非常困难的,迄今为止只求出9个Ramsey数的准确值.探讨了DNA生物分子超级计算在求解这一困难数学问题的可能性.将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,在许进等人提出来的位序列编码方法的基础上,提出一种用于求解Ramsey数的DNA计算模型与算法.从下界开始,直到上界,每次产生问题的解空间,然后根据Ramsey数的定义,删除满足特定条件的解,最后检测最终的试管以确定当前值是否为所要求的Ramsey数,最终得到具体的Ramsey数值.算法性能理论分析和模拟实验结果表明了本算法在求解Ramsey数的理论可能性.
展开▼
