|
In the past 10 years, a lot of achieve has been made in the DNA computing, particularly in the SAT problem, currently,like Lipton, Adleman, Qinghua Liu et. al. have made great progress in this field. In this paper I continue with the work about 3-SAT problem’s effect algorithm of my pioneers, here I give four method and eight kinds of algorithm: The first method is self-assembly algorithm, in terms of self-assembly theory, I device the function aera, and device the Algorithm itself, the idea is simple , that is to find those strings from m test tubes which may satisfy each of clauses respective, then put this strings to one test tube together, they will self-assembly with enzymes’help to find the commonality strings, that is the formula’s solution. The second method is fluorescence sign algorithm , it is a kind of method of self-assembly in nature, the idea is just like the first one, the difference is that it to find commonality strings with probe model, and it’s space complexity is smaller than the first one. The third method is three-link algorithm, it is the first one’s improve algorithm, it adopt three-link way to device, and take three test as one unit to self-assembly, and use the same way to carry out. The forth method is three-split algorithm, this is a split strategy, first to reset all variables in terms of the numbers of the variable which it take place in the clause, then by the algorithm of slope to exact the split point of k, further to make sure the second split point, that is to distribute all variable to parts, then split all clause to four parts, that is to say the Boolean formula is split into four sub-formula, This four methods and eight kinds of algorithm, the first three algorithm the base algorithm of this paper, the common of this three methods is to improve the parallelism of algorithm by the model of self-assembly, then to reduce the complexity of algorithm’s time to constant, but the space complexity of algorithm is no better than others. The last method overcome front algorithm’s fault, as it reduce the time complexity to constant, simultaneity it reduce the space complexity more smaller than others.
|