Using three dimensional graph structure and DNA self-assembly we show that theoretically 3-SAT and 3-colorability can be solved in a constant number of laboratory steps. In this assembly, junction molecules and duplex DNA molecules are the basic building blocks. The graphs involved are not necessarily regular, so experimental results of self-assembling non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections are presented.
- Junction molecules
ASJC Scopus subject areas
- Theoretical Computer Science
- Hardware and Architecture
- Computer Science Applications