Algorithm of Solving the Subset-Product Problem Based on DNA Tile Self-Assembly

摘要

DNA tile self-assembly is a promising paradigm for nanotechnology. Recently, many researches show that computation by DNA tile self-assembly may be scalable. In this paper, we mainly propose the algorithm of solving the subset-product problem based on DNA tile self-assembly, including constructing three small systems which are nondeterministic guess system, multiplication system and identification system, by which we can probabilistically get the solution of the subset-product problem. Our model can successfully perform the algorithm in polynomial time with optimal O(1) distinct tile types, parallely and at very low cost.