图论中NP完全问题的DNA计算

猜想: 不存在解NP完全问题的多项式时间的算法。它是目前计算机科学和数学最大的未解问题之一。10多年DNA计算机的研究表明，它具有高度的并行性、大容量和低消耗，它在解决图论或者组合优化中的NP完全问题上比电子计算机具有一定的天然优势。本项目图论中NP完全问题的DNA计算是计算机科学、数学和生命科学的一个综合性课题，拟建立具有一定通用性的DNA计算模型，用它解组合优化中若干计算问题，如整数线性规划问题等；拟对DNA计算中的误差问题和解空间指数爆炸问题进行研究，降低生物操作数目，减少误差，提高有效解形成的可能，克服解空间指数爆炸问题。拟对新的图类DNA标号图进行系统地研究，扩大它的适用范围，如在DNA计算和测序方面等。进一步研究分子计算系统中有效的生物技术。为用DNA计算机解决组合最优化中的计算问题和相关图论问题的研究打下良好的基础。