Proof. Recall that if ur is horizontally instantiated, then Ix(fr) s Ix(ur) s Ix(f¬r) and Ix(fr) s Ix(u¬r) s Ix(f¬r); if u¬r is horizontally instantiated, then Ix(ur) s Ix(fr) and Ix(f¬r) s Ix(u¬r) s Ix(f 0 r
) (cf. Figure 7). Furthermore, note that the top edges of the mbrs of these regions are on the same line. It is easy to see that M(ur) (M(u¬r), resp.)
bridges the gap between M(w c 0
) and M(w c rs) if ur (u¬r, resp.) is horizontally instantiated and pr is positive (negative, resp.) in the clause. Note that u
∗
r = ur (u
∗
r = u¬r, resp.) if pr is positive (negative, resp.) in the clause. The proposition follows directly.

We now show that Nc has the following property.

Proposition 4. Suppose Nc *is the basic CDC network defined for clause* c = p
∗
r ∨ p
∗
s ∨ p
∗ t
(r < s < t). Assume, moreover, π : V → {true, false} is a truth assignment. Then the following statements are equivalent:

```
- π satisfies c, that is, at least one of the three literals p
                                            ∗
                                            r
                                             , p
                                               ∗
                                               s
                                                , and p
                                                     ∗
                                                     t
                                                      is true under π;

```

- Nc has a solution in which uiis vertically instantiated iff π(pi) = true fori = *r, s, t*.

Proof. We first prove that, if π does not satisfy c, then Nc has no solution in which uiis vertically instantiated iff π(pi) = true for i = *r, s, t*. Or equivalently, if π(p
∗ i
) = false for i = *r, s, t*, then Nc has no solution in which u
∗
i is horizontally instantiated for i =
r, s, t. We prove this statement by contradiction. Suppose Nc has a solution in which u
∗
i is horizontally instantiated for i = *r, s, t*. Then, by Proposition 3, u
∗
r bridges the gap between M(w c 0
) and M(w c rs); u
∗
s bridges the gap between M(w c rs) and M(w c st); and u
∗ t bridges the gap between M(w c st) and M(w c 1
) (cf. Figure 9). Let

$$i=r,s,$$
$$A_{c}={\mathcal{M}}(v_{c})\setminus(\bigcup\{{\mathcal{M}}(x):x\in X_{c}\}),$$

where Xc is defined as in Eq. 33. It is clear that M(Ac) is a proper subset of M(vc).

Because the interior of vc is disjoint from M(x) (x ∈ Xc), we have vc ⊆ Ac. This leads to a contradiction. Therefore, if π does not satisfy c, then Nc has no solution in which ui is vertically instantiated iff π(pi) = true for i = *r, s, t*.

On the other hand, suppose π satisfies c. We construct a solution of Nc in which uiis vertically instantiated iff π(pi) = true for i = *r, s, t*. Variables in NV other than ui, u¬i (1 ≤ i ≤ n) are defined as the same in Example 3.

For each propositional variable pi, we define ui and u¬i as follows (cf. Figure 5).

$$u_{i}=\left\{\begin{array}{ll}[i,i+0.2]\times[0.5,1],&\mbox{if$\pi(p_{i})$is true,}\\ [i,i+0.5]\times[0.8,1],&\mbox{otherwise.}\end{array}\right.\tag{42}$$  $$u_{-i}=\left\{\begin{array}{ll}[i,i+0.7]\times[0.6,1],&\mbox{if$\pi(p_{i})$is true,}\\ [i,i+0.4]\times[0.3,1],&\mbox{otherwise.}\end{array}\right.\tag{43}$$
