literal是? 有一變數x x的值為0或1(布林數) 則x和x'即為literal 若x=0則x'=1 反之亦然 clause是? y1,y2,......,ym為literal y1 V y2 V......V ym即為clause(V代表or) CNF(conjugate normal form)是? C1,C2,......,Cn為clause C1 ^ C2 ^ ....... ^ Cn為CNF k-CNF是? 每個Clause裡最多可以有k個literal 3-SAT的問題是? input:3-CNF output:3-CNF是否會有true的解 independent set problem 給定一個G(V,E)和整數k 是否存在一個G上點的子集合S,對G的每個edge至多會有一點屬於S,使S的點數<=m? 1.轉換的演算法 3-SAT的input為p,p是一個3-CNF independent set的input為g(p),m是三角形的數量 g(p)圖形是 將p的每個literal當成一個vertex a.同一個clause的literal都有edge形成一個三角形 b.對任意的literal x和x'都有edge c.若一個clause不足三個literal則取同一個clause的literal補足 independent set的output是true則3-SAT的output是true 反之亦然 2.轉換的時間 input:O(literal^2) output:O(1) 3.正確性 p 滿足 SAT if g(p),m有independent set 若g(p),m有independent set則g(p)每個三角形會有一個literal屬於independent set 則p會是true g(p),m有independent set if p 滿足 SAT 若p滿足SAT則每個clause至少有一個literal是true 從每個clause中取一個為true的literal 放入g(p)圖中,則g(p)中的每個vertex必不相鄰 因為一個三角形只有一個independent set 而每個三角形的independent set也不相鄰 因為任意不同的兩三角形只有literal x和x'才會有edge --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.7.59 ※ 編輯: ajnightmare 來自: 58.114.209.65 (05/25 00:04) ※ 編輯: ajnightmare 來自: 58.114.208.7 (06/19 00:27)