Np Complete 4tl2t

2

0

1

1

0

1

0

0

1

1 Clause i

0

2

Theorem 9.8

To Begin 

 

Arguably the most important decision in deg an NP-completeness proof is, from which NP-complete problem to start. However, there are no easy rules here. Always start with 3SAT, an extremely versatile problem which can be easily reduced to a surprising range of NP-complete problems. So what does reduction mean?

Reducible Definition We say that language L1 is reducible to L2 if there is a function R from strings to strings computable by a deterministic Tuning machine is Space O(log n) such that for all input x the following is true : x ∈ L1 if and only if R(x) ∈ L2 . R is called a reduction from L1 to L2.

That problem is NP-complete. We infer a reduction from (3)SAT to that problem Circuit-SAT Cook's Theorem. Circuit-SAT ∈ P  NP=P

{σ(c) | c 為一 circuit with variables, 且存在一 true assignment 可使 c 之值為 true }

Prerequisite – NAESAT is NP-complete (P187) 

In 3SAT we are given a set of clause with three literals in each, and we are asked whether there is a truth assignment T such that no clause has all three literals true. n

3-SAT  {σ(Φ) | Φ = Λ Ck , Ck 都是 clause, 且 |Ck|≦3 , 又存在一種 true k=1 assignment 可使 Φ 為 true}  

Based on 3-SAT, in no clause are all three literals equal in truth values, which means NAEST. {存在一種 truth assignment 使得 Ci 中之三個 literals 有 true 有 false} 只需證明 Circuit-SAT 可 Reduce 到 NAESAT. 考慮 C 為一 Circuit : g7 O

Circuit-SAT {σ(c) | c 為一 circuit with variables, 且存在一 true assignment 可使 c 之值為 true }

g1↔x1

g6 v g4 Λ g1

x1

g5 ┐ g2

x2

g3

x3

(x1→g1) Λ (g1→x1) and (x1→g1) = (┐x1 v g1) and (g1→x1) = (┐g1 v x1) So (x1→g1) Λ (g1→x1) = (┐x1 v g1) Λ (┐g1 v x1)

g(True) means (g) g(False) means (┐ g)

Clause 含一個或兩個 literal, 可以補一個 false 的 literal 使得最後 結果不變, 但是可以滿足 NAESAT. 如果 Clause 含三個 literal 只 有兩種可能…

Prerequisite – NAESAT is NP-complete (P187) 如果 Clause 含三個 literal 只有兩種可能… h Λ

g1

x1

g2 x 2

 g1 Λ g2 ↔ h Equal to (g1 Λ g2 → h) Λ (h → g1 Λ g2) And (g1 Λ g2 → h) = ┐(g1 Λ g2) v h = (┐g1 v ┐g2 v h) -> Has three literals And (h → g1 Λ g2) = ┐h v (g1 Λ g2) = (┐h v g1) Λ ( ┐h v g2) (┐g1 v ┐g2 v h) = true

x1

┐g 2

h

v=(┐g1 v ┐g2 v h)

T(F)

T(F)

F

T

F(T)

T(F)

F

T

T(F)

F(T)

F

T

F(T)

F(T)

T

T

 g1 v g2 ↔ h We will have a three literals clause : (g1 v g2 v ┐h)

h v

g1

┐g 1

g2 x 2

由上面推導可知道 Circuit-SAT 可以 Reduce 到 NAESAT, 故 NAESAT 也是 NP-complete!

g1

g2

┐h

v=(g1 v g2 v ┐h)

T

T

F(T)

T

F

T

F(T)

T

T

F

F(T)

T

F

F

T(F)

T

Theorem 9.8 : 3-COLORING is NPcomplete (P198)  Suppose that we are asked to “color” the vertices of a given graph with k colors such that no two adjacent nodes have the same color. This classical problem is called kCOLORING. When k=2 it is quite easy to solve. For k=3 , it is 3-COLORING. 1 0

0 2

3-Coloring : {σ(G),K : G=(V,E) be an undirected graph there each vertex can be colored in K(0,1,2) and no adjacent vertex has some color.}

2

0

Theorem 9.8 3-COLORING is NP-complete Proof: • We are given a set of clauses C1,…,Cm each with three literals, involving the three variables x1,…,xn, and we are asked whether there is a truth assignment on the variables such that no clause has all literals true, or all liter false. • We construct a graph G, and argue that it can be colored with colors {0,1,2} if and only if all clauses can take diverse values. • Each clauses Ci is represented by a triangle, [Ci1, Ci2, Ci3]. We claim that G can be colored with colors {0,1,2} if and only if the given instance of NAESAT is satisfiable. Ci2

Ci1

CI3

If Cij takes the color 1 we think that the variable is true, otherwise it is false and takes the color 0.

Theorem 9.8 : 3-COLORING is NPcomplete Theorem 9.8 3-COLORING is NP-complete (P198)

Proof: • How can the clause triangles be colored? If all literals in a clause are all true, then the corresponding triangle cannot be colored, since color 1 will be adjacent; so the overall graph is not 3-colorable. Similarly if all literal are false. This completes the proof of one direction. 1 1

•

0 2

2

0

For the other direction, suppose that a satisfying (in the NAESAT sense) truth assignment exists, we color node a by color 2, and the variable triangles in the way that reflects the truth assignment. And for any clause, we can color the clause triangle as follows: We pick two literals in it with opposite truth values and color the vertices corresponding to them with available color among {0,1}; we then color the third node 2. ┐X =1 i

Xi=0

a=2

Theorem 9.8 : 3-COLORING is NP-complete (P198) Reduction from NAESAT to 3 Coloring Here we tell how this graph is related to NAESAT: • Consider below 3SAT. Each variable will be a triangle on the top of graph : (x1 ν x2 ν x3) Λ (┐x1 ν ┐ x2 ν ┐ x3) Λ (┐ x1 ν ┐ x2 ν x3) Here we have variables x1, x2 and x3. So we have a initial graph on top. • Then we treat each clause as a triangle in the bottom of graph : • Connect top of graph with bottom of graph according to the name of variable. • Finally, choose a true-assignment make the formula to be true and assign value to each variable on the top of graph. For example, x1=true, x2=false, x3=true. • Then the corresponding connected variable in the bottom take the opposite value. Because the formula is NAESAT satisifiable, we can find a value pair in opposite and the third node given a value 2 : 2

x1:1

Opposite value pair

┐x

1:0

┐x

┐x

x2:1 ┐x

x1:0

x2:0

x3:2

1:1

2:1

┐x

x3:1

3:0

┐x

2:0

┐x

3:2 ┐x

1:1

2:0

x3

Extra : 2-Coloring is Polynomial 

Bipartite graph : A bipartite graph (or bigraph) is a graph whose vertices can be divided into two dist sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. Bipartite  {σ(G) | G=(V,U,E) be an undirected graph there exist two dist sets U,V of nodes which only connected to the node of the opposite set.}



Testing bipartiteness : If a bipartite graph is connected, its bipartition can be defined by the parity of the distances from any arbitrarily chosen vertex v: one subset consists of the vertices at even distance to v and the other subset consists of the vertices at odd distance to u. Thus, one may efficiently test whether a graph is bipartite by using this parity technique to assign vertices to the two subsets U and V, separately within each connected component of the graph, and then examine each edge to that it has endpoints assigned to different subsets.

V = {0,2,4} U = {1,3,5}

Extra : 2-Coloring is Polynomial 

Testing Algorithm : Base on the idea from previous slide, we use BFS (Breadth-First Search) which has running time O(V+E) on G(V,E). Consider below graph and the start search vertex is x1. For BFS, the search order would be : 4st round

2st round

x5 x2

5st round x8

x6 x3

x1 x3

x9

6st round

x7 1st round



3st

round

Mapping from Bipartite Graph to 2-Coloring : Based on the introduction on Bipartite, we can regard Bipartite Graph Testing is polynomial problem. So once we treat value{0,1} in Bipartite Graph to be color K{0,1}, we can use the algorithm BFS to whether a Graph is 2-Coloring satisfiable which means the 2-Coloring is Polynomial.

Reference    

 

 

http://www.cs.uky.edu/~lewis/cs-heuristic/text/class/more-np.html http://en.wikipedia.org/wiki/Graph_coloring http://www.ic.unicamp.br/~rezende/ensino/mo417/2010s2/notas/16nphard.pdf http://www.facebook.com/l.php?u=http%3A%2F%2Fwww.idoub.com%2Fdo c%2F74771574%2FNPComplete&h=JAQFd2bx9AQHfvtHscNUNOAWds2NPGH1vVERHNVkABiPL tg [ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤 - 先廣後深法 [ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤 [ 資料結構 小學堂 ] 圖形結構 : 圖形表示法 [ 資料結構 小學堂 ] 圖形結構 : 圖形介紹