METHOD FOR SOLVING NP-COMPLETE PROBLEMS

摘要

A method aiming at solving NP-complete problems (for example, a clausal form Boolean formula) by using the characteristic of single-stranded DNA molecules of forming the secondary structure. In a clausal form Boolean formula which is expressed in m variables (for example, a to f) and n clauses (for example, clauses 1 to 10) and in which each of these n clauses contains m variables exclusively (for example, a formula wherein each clause is selected from 3 variables), each variable is expressed by, for example, a DNA molecule having 30 residues. Each clause is specifically expressed by both ends of the base sequence showing the variable or the base sequence of a linker attached to one end. By mixing DNA molecules having linkers, these DNA molecules are ligated with each other by enzymes to form products consisting of n molecules ligated linearly. From these products, DNA molecules not corresponding to the solution with the hair pin structure are removed, thereby providing the solution.