DNA tile assembly model for 0–1 knapsack problem

摘要

Research results shows that reasonable solution for NP-complete problem could be achieved using DNA self-assembly model, in which the parallel computing ability of DNA computation could be get a full play. In DNA computing paradigm, the information is encoded in DNA tiles, which can be self-assembled via sticky-end associations. In this paper, the DNA self-assembly model for 0–1 knapsack problem is constructed. This model is composed of three units: nondeterministic guess system, adder system and comparator system. Results shows that the three systems can be carried out in polynomial time with optimal 0(1) distinct tile types in parallel. All of these demonstrate the feasibility of DNA tiles self-assembly for NP-problems.