摘要
合取范式化为析取范式的计算复杂度是指数级别的,为了降低它的计算复杂度,提出了合取范式化为析取范式的DNA表面计算.因为DNA中碱基对的配对可以同时进行,所以DNA表面计算具有并行计算能力,它实现了将合取范式化为析取范式的计算复杂度降低到多项式级别.
Since the computational complexity in converting conjunctive normal form into disjunctive normal form is ex ponentially graded, therefore, in order to simplify the computational complexity, a surface-based DNA algorithm for the con version of normal form transforming into disjunctive normal form is put forth. Because DNA base pairing can take place simul taneously, the surface-based DNA algorithm is capable of parallel computation, which makes it possible to lower the computa tional complexity of converting conjunctive normal form into disjunctive normal form to that of a polynomial operation.
出处
《内江师范学院学报》
2009年第6期14-16,共3页
Journal of Neijiang Normal University
基金
四川省教育厅青年基金(07ZB043)
关键词
合取范式
析取范式
DNA表面计算
conjunctive normal form
disjunctive normal form
DNA algorithm
