3-Conjunctive Normal Form (3-CNF)

3-CNF Satisfiability

3-Conjunctive Normal Form (3-CNF):

A Boolean formula that is an AND of clauses, each of which is an OR of exactly 3 distinct literals.

e.g.

3-CNF-SAT = { <ψ>:ψis a satisfiable 3-CNF }

Theorem:

It is obvious that

Now we need to construct the reduction algorithm

Step 1: Construct a binary parse tree for the input formulaψ, with literals as leaves and connectives as internal nodes.

see. Fig.36.9 for the parse tree of

Step 2: Just as we did in pervious theorem, assign a variable for each output of internal node. Thus, the original formula ψcan be rewritten as the AND of the root variable and a conjunction of clauses describing the operation of each node.

see. p.944 for an example

Now each clause has at most 3 variables but is not in disjunctive normal form.

For each clause ψi , identify all possible truth assignments that evaluate it to 0.

Using these assignments, we build a formula in disjunctive normal form that is equivalent to .

The CNF ofψi can be converted by applying DeMorgan’s law. See p.944 for an example.

Step 3: We need to convert each clause Ci with less than 3 literals to that with exactly 3 literals.

Case 1. If Ci has 2 literals, say , we can convert it to

Case 2. If Ci has 1 literal, say l, we can convert it to

The resulting formula after this conversion is satisfiable iffψis satisfiable.

Besides, the reduction can be done in polynomial time:

Step 1: It introduces at most 1 variable and 1 clause per connective inψ.

Step 2: Constructing from introduces at most 8 clauses into for each clause in .

Step 3: Constructing from introduces at most 4 clauses for each clause of .

Therefore, both the size of the final formula and the time for construction is polynomial to the size of the input formula.

NP-Complete Problem

See Fig 36.11 for the proof roadmap

Def. A clique in an undirected graph G=(V, E) is a subset of vertices, each pair of which is connected by an edge in E.

Def. The clique problem is to find a clique of maximum size in a graph

The brute-force algorithm takes

Theorem.

The verification algorithm takes G and a subset V’ of V vertices as the certificate. It checks whether V’ is a clique in polynomial time by checking whether, for each pair , the edge .

Lemma.

Let be a Boolean formula in 3-CNF with k clauses, where .

For each clause Cr, place a triple of vertices V1r, V2r, V3r.

Regarding edges, 2 vertices iff

2. lir and ljs are consistent, i.e. lir is not the negation of ljs.

See Fig 36.12 for an example

This graph can be computed in polynomial time (why?)

To show that this transformation of ψinto G is indeed a reduction, we show

Supposeψhas a satisfying assignment. Therefore, each clauses Ci contains at least one literal lir that is assigned 1. Besides, any pair of such literals must be consistent. Therefore, pick one such literal from each clause yields a set of V’ of k vertices and V’ must be a clique.

Suppose G has a clique V’ of size k. V’ contains exactly one vertex per triple. Assigning 1 to each literal lir s.t. yields a satisfying assignment.

See Fig 36.12 for an example

Vertex Cover Problem

Def. A vertex cover of G=(V, E) is a subset V’ of V s.t. if , then either

Optimization problem: Find a vertex cover of minimum size.

Decision problem: Determine if there exists a vertex cover of size k.

Theorem.

Proof.

The verification algorithm takes G=(V, E) as the input and a subset V’ of V of vertices as the certificate. It checks if and if every edge , whether . The execution time is polynomial.

We show

Suppose <G, k> is the input of the clique problem. We take as the input of the vertex cover problem. To show that the transformation is a reduction, we show

Let V’ be a clique of size k in G. Then for every , that is,V-V’ is a vertex cover of

Let V’ be a vertex cover of , then for every ,

i.e. . In other words, V-V’ is a clique of G.

Ex. 36.5.2 in p.960

The subset-sum problem

Theorem.

Proof.

The verification algorithm take S and t as input, and a subset S’ of S as the certificate. It checks if .

Note that both and the verification is polynomial to

We show

A Graph G=(V, E) can be represented as a 0-1 incidence matrix

Note that each column in the incidence matrix has exactly two 1’s.

For each vertex Vi, create an integer xi whose base-4 representation consists of a leading 1 followed by digits as in the incidence matrix.

For each edge create an integer that is just a row in the identity matrix.

i.e. See Fig 36.14 for a visual example

To construct t, it is observed that a vertex cover of size k consists of k vertices, and therefore kxi’s. Besides, each edge must be covered by at least one vertex. (and at most 2). So we define . This reduction, of course, is polynomial time to <G,k>.

We then need to show

Let V’ of size k be a cover of G,

It is clear

Suppose , and

We claim m=k and is a vertex cover of G.

V’ is a vertex cover because for each edge, at least one and at most 2 xi’smust contribute to the sum.

m=k because the only way the leading k in target t can be achieved is by including k of the xi’s in the sum.

The Hamiltonian-cycle problem

Theorem.

Proof.

The verification algorithm takes G=(V, E) as the input and a list of V as the certificate. If checks if each pair of adjacent vertices form an edge in E.

Note that both the list and the verification time is polynomial to .

We show

Consider the A type widget show in Figure 36.15

aa’

b b’

Note that (a, a’) and (b, b’) are exclusive in any Hamiltonian cycle.

Consider the B-type widget shown in Figure 36.16

The property with B-type widget has been that there does not exist any Hamiltonian cycle that connects (b1, b2), (b2, b3), (b3, b4) at the same time.

We now construct a graph consisting of copies of these 2 widgets from a 3-CNF formula ψ.

Each clause inψis represented by a copy of widget B, and these widgets are serially connected. See Fig 36.17
Each variable xm inψis represented by a cycle consisting of at least 2 vertices xm’and xm’’.

Let the 2 edges (or paths) between xm’and xm’’ be denoted as em and respectively.

Letψij be the j’th literal of i’th clause inψ, 1<=i<=k. Ifψij = xm, construct a A-widget between emand (bij, bi,j+1).
If ψij=, construct a A-widget between and (bij, bi,j+1).

We now want to show that formula ψis satisfiable iff G contains a Hamiltonian cycle.

Let the cycle be h. It must follow (b1,1, x1’), a path connecting x1’ and xm’’, (xm’’,

bk,4), a path connecting bk,4 and b1,1.

For the path (e1’, e2’,…,em’) connecting x1’ and xm’, we define a truth

assignment (x1, x2,…, xm) wherex1=1 iff e1’= e1

and x1=0 iff

For B-widget (bi1, bi2, bi3, bi4) of each clause i. If (bi1, bi2) is in h, the other

edge in A-widget must NOT in h. In other words ψij evaluates 0.

However, it is clear not every (bij, bi,j+1), j=1, 2, 3 is in h (because of the

property of B-widget).

Therefore ψi is evaluate to 1, for .

Let ψis satisfied by some truth assignment. By following the same rule, we can

construct a Hamiltonian cycle for G. These rules can indeed be followed.

Finally, we note that graph G can be constructed in polynomial time because there are k B-widgets, one for each clause in ψ, and 3k A-widgets. Since each widget is of fixed size, the graph G has O(k) vertices and edges. Thus, this reduction can be done in polynomial time.

The traveling-salesman problem

The traveling salesman problem: Given a complete graph, where each edge is associated with a cost, find a tour or a Hamiltonian cycle, such that the total cost is minimal.

Theorem.

Proof.

The verification algorithm takes G, C, K as the input and a list of V in the tour as the certificate. It verifies whether the cost incurred to the list is no larger than K.

Let G=(V, E) be an instance of HAM-CYCLE. We construct another graph

G’=(V, E’), where , and the cost function

The instance of TSP is then (G’, C, 0), which can be formed in polynomial time.

The proof of G is Hamiltonian iff G’ has a tour of cost at most 0 is straightforward.