DOC

3-CNF Satisfiability

By Tammy Miller,2014-05-07 10:29
8 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