SAT问题的主要算法模型

摘要

DNA计算是一种以分子生物学为基础的全新算法。较之电子计算具有较高并行性，可为电子计算机在多项式时间内解决不了的NP-完全问题的提供解法。这里主要介绍了DNA计算所研究的，目前取得了较大进展NP完全问题--SAT(可满足性)问题具有代表性的几种算法模型：试管模型、表面基模型和自装配模型以及优化搜索算法模型的设计思想和算法。最后在对它们的算法复杂度进行分析比较的基础上提出解决SAT问题发展的看法。