Information Technology Reference
In-Depth Information
X
X
Y
Z
X
T(C1)
T(C3)
T(C2)
Y
Y
Y
S(C1)
T(C4)
S(C2)
S(C3)
S(C4)
Z
Z
Z
X
Fig. 2.30
3-SAT solutions represented by graphs encoding assignments
by means of two sticky ends (left and right) with the literals of the previous clause
(on the left) and with the literals of the next clause (on the right, see Fig. 2.31).
Moreover, for every variable
X
, let the literal
X
be encoded with a string that is the
the mirror of the encoding of
X
. Of course, literals of the first clause are linkable
only with those of the second, while literals of the last clause are linkable only with
those of clause of order
m
¬
1(
m
number of clauses). In this way, if a a path, of
linked literals, is formed where a variable and its negation are encoded, then a DNA
hairpin is formed. Therefore, in general with
n
variables, the true solutions are the
paths encoding
n
literals that are not DNA hairpin.
−
T(C3)
T(C1)
T(C2)
S(C1)
T(C4)
S(C4)
Lit(C1)
S(C2)
Lit(C2)
S(C3)
Lit(C4)
Lit(C3)
Fig. 2.31
3-SAT solutions represented by sequences encoding literals
T(X1)
S(X2)
Cla(X2)
T(X3)
S(X1)
Cla(X1)
T(X2)
S(X3)
Cla(X3)
Cla(
X1)
Cla(
X2)
Cla(
X3)
S(X1)
T(X1)
S(X2)
T(X2)
S(X3)
T(X3)
Fig. 2.32
3-SAT solutions represented by sequences encoding clauses
An algorithm due to Manca and Zandron [46] provides 2
n
strings (
n
number of
boolean variables)
Cla
is a
sequence (double string with sticky ends) of DNA encodings of all clauses having
the literal
X
i
,and
Cla
(
X
i
)
and
Cla
(
¬
X
i
)
,for1
≤
i
≤
n
. The string
Cla
(
X
i
)
(
¬
X
i
)
is a sequence of DNA encodings of all clauses having
the literal
¬
X
i
. Moreover,
Cla
(
X
i
)
and
Cla
(
¬
X
i
)
are left-linkable to
Cla
(
X
i
−
1
)
and
to
Cla
(by
means of suitable sticky ends, see Fig. 2.32). It is easy to show that the solutions
of a 3-SAT problem are represented by those strands which encode sequences of
n
strings of type
Cla
((
¬
X
i
−
1
)
, while they are right-linkable to
Cla
(
X
i
+
1
)
and to
¬
Cla
((
¬
X
i
+
1
)
containing the encodings of all the clauses of the given
problem. In the case of
m
clauses,
m
extractions are sufficient to solve a 3-SAT
problem.
(
−−
)
