[演算] 3-SAT & independent set
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
推
05/24 20:41, , 1F
05/24 20:41, 1F
※ 編輯: ajnightmare 來自: 58.114.209.65 (05/25 00:04)
※ 編輯: ajnightmare 來自: 58.114.208.7 (06/19 00:27)