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)