关键词: DNA计算 NP完全问题 子集积问题 分治法

Abstract:

the DNA-based computation has been applied to many scientific problems, and how to decrease the number of DNA strands increasing exponentially in these applications is very important in the research on DNA computers. For the objectivity of the solution to the subset-product problem which is a famous N  P-complete problem with the DNA computer, the strategy of divide and conquer is introduced into the DNA-based supercomputing and a DNA algorithm is proposed. The proposed algorithm consists of an rrbit parallel Searcher, and other five sub-procedures. It is demonstrated that the proposed algorithm can f irst reduce the number of DNA library strands from O（2q） to 0（2^q/2） to solve a q-dimensional subset- product instance, while keeping the polynomial  l operation time unchanged. This paper shows that the traditional technology can still bear importance even in designing DNA computer algorithms. Furthe rmore, this work indicates that the cryptosysterns using public keys are perhaps insecure, because theoretically, the 120-variable subset-product public   key can be easily broken provided that the technology of DNA computers is mature.

Key words: （DNA-based computin, NP-complete problem： subset-product problem, divide and conquer）