在过去的10 年中,DNA 计算取得突飞猛进的成果,尤其是在SAT 问题上,以Lipton , Adleman , Qinghua liu 等人为代表的科学家们纷纷在SAT 问题上,取得了可喜的成果。本文则在前人的基础上继续探索3-SAT 问题的有效算法,并给出了4 种方法的8 个算法第一种算法为自装配算法,根据自装配的原理,设计了链接方式,设计的思想非常简单明了,那就是首先在m 个试管中分别找到可以使m 个子句各自为1的链,然后再将找到的这些链全都倒入同一个试管中,利用自装配方法一步找到公共链,也就是公式的解。第二种方法为荧光标记法,它是自装配算法的一种,只不过他采用了荧光标记的方式,它的设计思路与第一种方法基本相同,所不同的是,在第二步将m个试管中的链到入同一个试管中之后,用的是探针模板来找公共解, 这也是一步完成的,与算法一的效果是一样的,只是它的空间复杂度要比算法一要小一些。第三种算法为三联接法,其实质上是算法一的一种改进算法,不过所采用的方式比起算法一要巧妙的多,它同过三联接的设计,较好的解决了时间复杂度的问题。它主要通过三联管的设计,以三个试管为一个单位,进行自装配,也就是分步自装配法,实现方法与第一种算法相同。第四种方法为三分法,,这是一种分支策略,首先对所有的变量通过其在子句中出现的数目进行变量重排,然后利用对斜率的算法,求出第一个分支点k,再根据不同的情况确定第二个分支点,从而将所有的变量分成三部分,根据这个划分,相应得创建三个子库,对于三个子库相应的将所有的子句划分成四个部分,从而将原来的公式划分成四个子公式。这样就将求原来的公式解得问题划分成求四个子公式的公共解得问题。这4 种方法的8 种算法,。前三种算法是本文的基本算法,它们的共同之处在于,通过自装配模型来实现了算法的高度并行,从而将算法的时间复杂度降低到了常量时间,而空间复杂度与其他算法相比却没有改进,而三分法则克服了上述缺点,在将算法的时间复杂度降低到了常量的同时,也将空间复杂度降低到了较小的水平。