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.
 
Search WWH ::




Custom Search