Complexity Classes - Models of Computation: Exploring the Power of Computing - page 364

x 3

x 1 x 1

x 2 x 2

x 3

Figure 8.15 A graph capturing the i m plications a ss ociated wit h the following satisfiable instance
of 2- SAT : ( x 3 ∨ x 2 ) ∧ ( x 3 ∨ x 1 ) ∧ ( x 3 ∨ x 2 ) ∧ ( x 1 ∨ x 2 ) ∧ ( x 3 ∨ x 1 ) .

condition hold and show that I is a “Yes” instance, that is, every clause is satisfied, which
contradicts the assumption that I isa“No”instance.
Identify a variable that has not been assigned a value and let α be one of the t wo cor-
responding literals such that there is no directed path in G from the vertex α to α .(By
assumption, this must hold for at least one of the two literals associated with x .) Assign
value 1 to α and each literal λ reachable from it. (This assigns values to the variables iden-
tified by these literals.) If these assignments can be made without assigning a variable both
values 0 and 1, each clause can be satisfied and I is “Yes” instance rather than a “No” one, as
assumed. To show that each variable is assigned a single value, we assume the converse and
show that the conditions under which values are assigned to variables by this procedure are
contradicted. A variabl e can be assigned contradictory values in two ways: a) on the current
step the literals λ and λ are both reachable from α and assigned value 1, and b) a literal λ
is reachable from α on the current step that was assigned value 0 on a p revious step. For
thefirstcasetohappen,theremu st beapathfrom α to vertic es λ and λ .Bydesignofthe
graph, if there is a path from α to λ ,ther e isapathfrom λ to α .Sincethereisapathfrom
α to λ ,theremustbeapathfrom α to α , contradicting the assumption that there are no
such paths. In the second case, let a λ be assigned 1 on the current step that was assigned 0
on a previous step. It follows t ha t λ w as given value 1 on that step. Becau se there is a path
from α to λ ,thereisonefrom λ to α and our procedure, which assigned λ value 1 on the
earlier step, must have assigned α value 1 on that step also. Thus, α had the value 0 before
the current step, contradicting the assumption that it was not assigned a value.
To s h ow t h a t 2 - SAT is in NL ,recallthat NL is closed under complements. Thus, it suf-
fices to show that “No” instances of 2- SAT can be accepted in nondeterministic logarithmic
space. By the above ar gu ment, if I i s a “No” instance, there is a variable x such that there is
apathin G from x to x and from x to x . Since th e number of vertices in G is at most linear

in n ,thelengthof I (it may be as small a s O ( √ n ) ), an NDTM can propose and then verify
in space O (log n ) apathin G from x to x and back by checking th at the putative edges are
edges of G ,that x is the first and last vertex on the path, and that x is encountered before
the end of the path.