Information Technology Reference
In-Depth Information
Possible
Solutions
True
Solutions
Solution
Extraction
In linear time
Space
Generation
In linear time
Fig. 2.27
The extract model
X
1
+
¬
X
2
+
X
3
(2.1)
X
2
+
X
3
+
¬
X
4
¬
X
1
+
¬
X
2
+
¬
X
3
X
1
+
¬
X
2
+
X
3
¬
X
2
+
¬
X
3
+
X
4
.
A natural way for generating a DNA space representing all possible assignments of
a 3-SAT is the Mix-and-split method, which is based on a very simple idea depicted
by Fig. 2.28 and expressed in TTL notation in Table 2.3.
Ta b l e 2 . 3
Mix-and-split procedure
Mix
X
1and
¬
X
1 in a tube
T
For J := 2 to
N
do
Split
T
into
A
and
B
Extend strands of
A
with
Xj
Extend strands of
B
with
¬
Xj
Mix
A
and
B
into
T
By using a split-and-mix procedure all assignments of a 3-SAT problem can be
generated and by applying to them
m
consecutive selection steps for filtering the
assignments satisfying all the clauses, then the required solution can be found. The
algorithm given in Fig. 2.29 is due to Lipton and provides 3-SAT solutions by means
of 3
m
extraction steps.