Solving the Satisfiability Problem with a Circular DNA Model

The Satisfiability Problem (SAT) is a research issue in the fields of computer science and mathematics, which focuses on determining whether there exists a truth assignment that satisfies a given Boolean expression (or propositional formula). This paper presents a circular model based on DNA strand displacement to address the SAT problem. Initially, a circular model incorporating input and output signals is designed, comprising an annular DNA strand, single strands attached to the annular DNA strand, and fluorescent labels. Subsequently, the variables in the SAT problem are transformed into DNA single strands using a variable transformation module. Through DNA strand displacement reactions, the single strands on the model can be displaced. Ultimately, by observing the remaining quantity of fluorescent signals in the solution, feasible solutions to the SAT problem can be identified. Additionally, simulation experiments are conducted using the Visual DSD simulation software to verify the effectiveness of the model. The research results indicate that this approach can effectively solve the satisfiability problem and provides new insights for applications in complex mathematical problems.