DOC

# 3-CNF Satisfiability

By Tammy Miller,2014-05-07 10:29
7 views 0
3-CNF Satisfiability

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.

(x1??x1??x2)?(x3?x2?x4)?(?x1??x3??x4)e.g.

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

? Theorem: 3?CNF?SAT?NPC

It is obvious that 3?CNF?SAT?NPC

Now we need to construct the reduction algorithm

SAT?P3?CNF?SAT

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 ? ? ((x1?x2)??((?x1?x3)?x4))??x2

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 ψ, identify all possible truth assignments that evaluate it to 0. i

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

equivalent to ??.

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

example.

Step 3: We need to convert each clause C with less than 3 literals to that with exactly i

3 literals.

(l1?l2) Case 1. If C has 2 literals, say , we can convert it to i

(l?l?p)?(l?l?p) 1212

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

(l?p?q)?(l?p??q)?(l??p?q)?(l??p??q)

1

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, V'?V

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

??CLIQUE??G,k?:Gisagraphwithacliqueofsizek

????VVV????????O(2) The brute-force algorithm takes ????VV?1????

? Theorem. CLIQUE?NPC

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

?u,v?V, the edge (u,v)?E.

3?CNF?SAT?pCLIQUE? Lemma.

??C1?C2???Ck Let be a Boolean formula in 3-CNF with k clauses, where

rrrC?l1?l2?l3,1?r?k. r

rrr For each clause C, place a triple of vertices V, V, Vr123.

rsRegarding edges, 2 vertices iff (V,V)?Eij

1. r?s

rsrs2. l and l are consistent, i.e. l is not the negation of l. ijij

2

? 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

1. Supposeψ has a satisfying assignment. Therefore, each clauses C contains i

rat least one literal l that is assigned 1. Besides, any pair of such literals i

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.

2. Suppose G has a clique V’ of size k. V’ contains exactly one vertex per triple.

rr?V?VAssigning 1 to each literal l s.t. i yields a satisfying assignment. i

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 (u,v)?E, then either

??u?Vorv?V

Optimization problem: Find a vertex cover of minimum size.

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

??VERTEX?COVER??G,k?:Ghasavertexcoverofsizek

? Theorem. VERTEX?COVER?NPC

Proof.

1. VERTEX?COVER?NP

The verification algorithm takes G=(V, E) as the input and a subset V’ of V

?(u,v)?Eof vertices as the certificate. It checks if and if every edge , whether V?k

??u?Vorv?V. The execution time is polynomial.

2. VERTEX?COVER?NP?HARD

CLIQUE?pVERTEX?COVER We show

? Suppose <G, k> is the input of the clique problem. We take ?G,V?k? as the

3

input of the vertex cover problem. To show that the transformation is a

reduction, we show

?G,V?k??VERTEX?COVERiff?G,K??CLIQUE

?

(u,v)?E?(u,v)?ELet V’ be a clique of size k in G. Then for every , u,v?V'

that is, V-V’ is a vertex cover of G

?

(u,v)?E Let V’ be a vertex cover of , then for every , u,v?V?V'G

i.e. . In other words, V-V’ is a clique of G. (u,v)?E

? Ex. 36.5.2 in p.960

The subset-sum problem

?? SUBSET?SUM??s,t?:thereexistsasubsetS'?Ss.t.t?s?s?S'? Theorem. SUBSET?SUM?NPC

Proof.

1. SUBSET?SUM?NP

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

Note that both and the verification is polynomial to S'S

2. SUBSET?SUM?NP?HARD

VERTEX?COVER?pSUBSET?SUM We show

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

ji1ifedgeeisincidenttov? ij..V?Estb??0otherwise?

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

? For each vertex V, create an integer x whose base-4 representation consists of a ii

4

leading 1 followed by digits as in the incidence matrix. E

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

jy?4i.e. i 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 k x’s. Besides, each edge must be covered by at least one vertex. (and at i

E?1Ejmost 2). So we define . This reduction, of course, is polynomial t?k?4?2?4?j?0

time to <G, k>.

? We then need to show

(G,K)?VERTEX?COVERiff(s,t)?SUBSET?SUM

?

??V'?Vi1,Vi2,...,Vik Let V’ of size k be a cover of G,

????S'?xi1,xi2,...,xik?yj:eisincidentonpreciselyonevertexinV' j

s?t It is clear ?s?S'

?

s?t????S'?xi1,xi2,...,xim?yj1,yj2,...,yjp Suppose , and ?s?S'

??V'?vi1,vi2,...,vim 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 xsmust i

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 xs in the sum. i

The Hamiltonian-cycle problem

? Theorem. HAM?CYCLE?NPC

Proof.

1. HAM?CYCLE?NP

5

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 . G

2. We show 3?CNF?SAT?pHAM?CYCLE

Consider the A type widget show in Figure 36.15

a a’

A

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

b1

b2

B

b3

b4

? 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 ψ.

1. Each clause inψ is represented by a copy of widget B, and

these widgets are serially connected. See Fig 36.17

2. Each variable x inψis represented by a cycle consisting of at m

’’ least 2 vertices xand x. m m

’’ Let the 2 edges (or paths) between xand xbe denoted as m m

eme and respectively. m

3. Letψ be the j’th literal of i’th clause inψ, 1<=i<=k. Ifψ = x, ijijm

construct a A-widget between eand (b, b). m iji,j+1

xmem4. If ψ=, construct a A-widget between and (b, b). ijiji,j+1

6

? We now want to show that formula ψ is satisfiable iff G contains a

Hamiltonian cycle.

?

Let the cycle be h. It must follow (b, x), a path connecting x and x’’, (x’’, 1,111mm

b), a path connecting band b. k,4k,4 1,1

For the path (e, e,…,e) connecting x and x, we define a truth 12m1massignment (x, x,…, x) where x=1 iff e= e 12m111

? and x=0 iff e1?e11

For B-widget (b, b, b, b) of each clause i. If (b, b) is in h, the other i1i2i3i4i1i2

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

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

property of B-widget).

Therefore ψis evaluate to 1, for . 1?i?ki

?

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.

?G,C,K?:G?(V,E)isacompletegraph,??

??TSP?CisafunctionfromV?V?Z, ??

??K?ZandGhasatourwithcostatmostK??? Theorem. TSP?NPC

Proof.

7

TSP?NP

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.

TSP?NP?HARD

HAM?CYCLE?pTSP

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

???G’=(V, E’), where E?(i,j):i,j?V, and the cost function

0if(i,j)?E? C(i,j)??1otherwise?

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.

8

Report this document

For any questions or suggestions please email
cust-service@docsford.com