A DNA solution of SAT problem by a modified sticker model.

Among various DNA computing algorithms, it is very common to create an initial data pool that covers correct and incorrect answers at first place followed by a series of selection process to destroy the incorrect ones. The surviving DNA sequences are read as the solutions to the problem. However, algorithms based on such a brute force search will be limited to the problem size. That is, as the number of parameters in the studied problem grows, eventually the algorithm becomes impossible owing to the tremendous initial data pool size. In this theoretical work, we modify a well-known sticker model to design an algorithm that does not require an initial data pool for SAT problem. We propose to build solution sequences in parts to satisfy one clause in a step, and eventually solve the whole Boolean formula after a number of steps. Accordingly, the size of data pool grows from one sort of molecule to the number of solution assignments. The proposed algorithm is expected to provide a solution to SAT problem and become practical as the problem size scales up.