Information Technology Reference
In-Depth Information
Fig. 2.28
Mix-and-split method
Fig. 2.29
Lipton's algorithm for 3-SAT. Expression
T
−
T
denotes the strands of
T
where
the extracted strands of
T
are removed.
We conclude by mentioning another three different ideas for solving 3-SAT in
terms of DNA computing. The first one due to Jonoska et al. represents a given in-
stance of the 3-Sat problem by producing, by means of DNA branches, a graph of
the type given in Fig. 2.30, where clauses are represented by joining double DNA
encodings of clauses (by means of branches as depicted in Fig. 2.17). Given a great
number of DNA structures representing the graph of a 3-SAT problem, we can pro-
ceed in
m
steps (
j
m
) by splitting, at step
j
, the pool of graphs in two pools and
cutting (by using specific enzymes able to recognize some strings and to cut them)
the literal
X
j
in the first pool and the literal
=
1
,
¬
X
j
, in the second pool, and then, by
mixing again the two pools. It is easy to verify that if the problem has solutions,
then a connected graph remains linking all the clauses, where each path of literals
represents a solution of the original problem.
An algorithm due to Sakamoto et al. yields solutions according to an idea similar
to that of Jonoska's algorithm. Let us suppose to order the clauses of a given prob-
lem. Let us encode the literals of every clause in such a way that they are linkable
