科学网 › 标签 › 3SAT

标签: 3SAT

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

3-SAT关联段子句消去法（详细解法）: 热度 1 accsys 2015-10-4 06:54; 3-SAT 关联段子句消去法姜咏江摘要：本文给出了 3-SAT 分段消去子句的求解算法。证明了可以在多项式时间求出 3-SAT 的解。从而证实斯提芬 . 库克定义下的 NP-complete 问题就是一个 P 类问题。。关键词： NP-complete ， P/NP 问题，子句消去法 1. 引言 P/NP 问题曾于 2000 年被美国克雷数学所定为最难的难题，有甚者说其挑战了人类智慧。所谓 P/NP 问题的定义是这样给出的：复杂度类 P 包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类 NP 由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。实际上这个定义有很多歧义，涉及到人们对确定型图灵机、非确定型图灵机、多项式时间、问题、决定问题、肯定解、给定正确信息、验证等一系列概念的认识的不统一，很难形成统一的见解。人们能够统一的是 P 类问题属于 NP 类问题，但 NP 类问题是否就是 P 类问题，一直没有确定的结论。 1971 年斯提芬 . 库克 (Stephen A. Cook) 发表了〈 The Complexity of TheoremProving Procedures 〉才把 P 之外的问题归结为三大类，即 NP 、 NP-complete 及 NP-hard 。库克的分类得到了学术界的认可。在库克的定义下， P 、 NP 、 NPC 、 NPH 问题的定义如下： P 问题，可以在多项式时间内求出解的问题， Polynomialproblem 。 NP 问题，可以在多项式的时间里验证一个解的问题， Non-deterministicpolynomial 。 NPC 问题，如果所有的 NP 问题都存在多项式时间算法使其能够归约为某一 NP 问题，则称该 NP 问题为 NPC 问题， NP-complete 。 NPH 问题，如果所有的 NP 问题都存在多项式时间算法使其归约到某问题，则称该问题为 NPH 问题， NP-hard 。由以上 NPC 问题的定义，我们不难想到，只要我们能够找到一个 NPC 问题，并能够找到其多项式时间的求解算法，那么就可以肯定这个 NPC 问题就是一个 P 问题。因为所有的 NP 问题都可以通过多项式时间算法归约成 NPC 问题，并且所有的 NPC 之间都有多项式时间算法实现转化。因而只要找到一个 NPC 问题的多项式时间算法，也就等于找到了所有 NP 问题的多项式时间算法，于是也就证明了 NP=P 。 2. 典型的 NPC 问题长时间以来，人们将寻找 NPC 类问题的多项式时间算法作为了解决 P=NP 问题的关键途径。一些典型的 NP 类问题（见图 1 所示）早已经被一些数学家明是 NPC 问题。例如， 3 元合取范式满足问题 3-CNF-SAT （简称为 3-SAT ）、子集和问题 SUBSET-SUM 、旅行商问题 TSP 、哈密顿回路问题 HAM-CYCLE 等，这些都是 NPC 问题寻找多项式时间解法的研究热门问题。但时至今日，尚未见到任何 NPC 问题的多项式时间复杂度的算法出现。本论文给出的是求 3-CNF-SAT 满足解的多项式时间复杂度的算法，还包括一些相关的概念和定理证明。这种算法只要将 3 换成 k 就可以得到 k-CNF-SAT 的解法。图 1 典型 NPC 问题及相关 3. 子句消去的算法子句消去法源自最简单的逻辑运算关系，即多个逻辑多项式之间的与运算结果为 1 ，必须每一个多项式的值为 1 才行。 3-SAT 每个子句多项式有 3 个变量，只要其中一个变量表示是 1 ，那么就可以将含有该变量表示的所有子句多项式消去，从而可以找到整个与运算表达式可能为 1 的那些解。一个个单独设置变量值，子句消去法不是一个多项式时间算法，但本文给出的分段子句消去法却有了惊人之处。 3.1 3-SAT 的定义所谓的 3-SAT 就是多个由 3 个逻辑变量或其非组成的多项式间形成与运算表达式。一般这种逻辑表达式被称为合取范式 3-CNF 。我们这里将逻辑或运算符用“ + ”表示，逻辑非运算符用“ ’ ”表示，而将逻辑与运算符省略。将逻辑变量或其非表示组成的多项式叫“子句”。例如， (x1’+x2’+x3’) (x1+x2’+x3’)(x1’+x2’+x4) (x3+x4’+x5)(x2’+x2+x3’) 是一个 3-CNF 合取范式，我们要求出满足 3-CNF=1 的那些解，这个问题习惯上人们称之为 3-SAT 。表达式中每个括号之间是与运算的关系，每个括号内的多项式就是子句。如果一个子句中包含一个变量和其非的项，那么显然该子句的值永远是 1 。我们称这样的子句是恒一子句。因为 3 元合取范式 3-CNF=1 中象 (x2’+x2+x3’) 这种恒一子句不影响求解，所以本文的 3-CNF=1 问题中不包括恒一子句，并用 3-SAT 替代它。 3.2 子句消去法与规定所谓的子句消去法，就是逐一设定变量的值，并将所有在变量值设定下值为 1 的子句消去，最终看是否剩余子句的算法。例如，合取范式 F=(x1’+x2’+x3’) (x1+x2’+x3’)(x1’+x2’+x4) (x3+x4’+x5) 我们令 x1=0,x2=0,x3=1 就可以将等式右面的全部子句消去（此处变量 x4 与 x5 的值可以任意设置），那么就可以得到 F=1 的一组 4 个解： 00100 、 00110 、 00101 、 00111 。为了方便又不失一般性，我们给出子句变量的概念和去除未参与构成子句变量的规定。定义 1 ：不论是逻辑变量 x 还是其非 x ’在一个子句中，我们都称 x 是这个子句的变量，叫子句变量。规定，我们研究的 3-SAT 既不不含无关的变量，也不包括恒一子句。 4. 3-SAT 格式表与反子句采用子句消去法要建立 3-SAT 表格式（见图 2 ），将子句以 3 位二进制数的形式写入表中。我们用 0 表示逻辑变量的非运算形式，用 1 表示逻辑变量本身，并称此种表示子句的二进制数为子句值。例如，用 000 表示子句 x i ’+ x j ’+ x k ’ ，而子句 x i + x j ’+ x k ’ 则用 100 表示。子句左面的变量叫开始变量，右面的变量叫结束变量。 4.1 合取范式的表格式 3-SAT 的规范表格式如图 2 所示。规定每个子句占用一行，并且要求变量相同的子句行相邻。图 1 合取范式值格式定义2 ：变量相同的子句放到一起叫子句块。图 2 中 3-SAT 表中颜色相同的部分就是一个子句块。当然，单独的子句也自成一块。按照从编号 1 顺序划分有 3 个相邻变量的子句块叫标准块。其它 3 个变量组成的块叫非标准块。非标准块中不相邻变量组成的块叫分散块。变量取值与其它子句块变量无关的块，叫独立块。两子句块开始变量相同，叫同根；结束变量相同叫同尾；子句块的开始变量到结束变量之间有其它子句块，这叫跨越。定义3 ：能够使子句块的子句全部消去的块中变量值叫块解。 3-SAT 一个子句块中子句值最多有 8 个，而块解最多只有 7 个。这一点下面会解释。为了清晰起见， 3-SAT 表将选择确定的变量值放到表下面的对应位置。 4.2 反子句与关联段两个数码之和为最大数码，一个就叫另一个的反码。二进制中数码 0 和 1 是互为反码。将一个数的数码都用其反码表示，叫原数的反码数，也简称反码。定义 4 ：子句块中子句值为反码的子句，一个叫另一个的反子句。 3-SAT 子句块的反子句最多有 4 对，用值表示分别是｛ 000,111 ｝｛ 100,011 ｝｛ 010, 101 ｝｛ 110,001 ｝。子句消去法求 3-SAT 满足解的算法，要用到关联段的概念。定义 5 ：有相同变量的子句块称为关联块，通过关联块形成的子句块集合叫关联段。能使关联段中所有子句值为 1 的段中变量值，称为段解。 3-SAT 有一元关联、二元关联。定义 6 ：子句块间有一个共同变量的子句块叫一元关联。子句块间有 2 个共同变量的子句块叫二元关联。 3-SAT 独立块间无变量关联。定义 6 ：在进行子句消去过程中由选择变量确定的子句形成的块叫动态块。能够使动态块子句消去的变量值叫动态块解。 5. 相关定理与性质为了说明子句消去法对 k ≥ 3 合取范式 k-CNF-SAT 求解的有效性，我们以更一般的情况来论述本节内容。子句消去法能够一次性求出 k-CNF-SAT 满足解基于如下的一些基本定理。定理1 ：子句块中若有互反子句存在，则互反子句值都不是块解。证明：依据子句消去法，以子句值消去的所有子句中不包括其反子句，因此总有一个子句值不能被消去。推论1 ： k-CNF-SAT 子句块解不超过 2 k -1 个。推论2 ： k-CNF-SAT 子句块中已有子句的反子句值不是块解。推论3 ：若 k-CNF-SAT 中有 2 k 个子句的子句块存在，则 k-CNF-SAT 无满足解。定理2 ：从一个子句块出发确定的解，也可以从另一子句块出发确定这个解。证明：假设由子句块 A 确定的解 a 不是由子句块 B 确定的解，那么因 a 中必含有 B 的一个子句值，于是可以从这个值出发，按照 a 的值扩充来求解，仍然是这个合取范式的一个解。于是可知，可以从 A 起始块或 B 做起始块得到相同的解。由此定理可知，选择任何子句块做为起始块求解，效果一样。推论4 ：从任意子句块出发都可能确定出合取范式的解。定理3 ：关联段无解，则 k-CNF-SAT 无满足解。证明：因为关联段解是 k-CNF-SAT 解的部分，其无解， k-CNF-SAT 自然无解。定理4 ： 3-SAT 有解的子句块确定了一个变量值，如剩下 4 个不同的值，则无段解。证明：由表1 可见，只要选值的两个变量值出现右侧的 4 个值，那么无论如何设值，都不能将其余子句消去。表 1 子句变量值表块子句可能值固定一个变量其它变量可取值 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 关联段性质：各关联段解相互独立。即一个关联段解改变，不影响其它段解。因为关联段解不独立，则说明这是一个关联段。推论5 ：动态块确定一个变量值后二剩余变量有 3 组值，则有惟一动态块解；两组或一组值，则有多个动态块解。定理5 ：连续多值可选的关联段最终可确定段解。证明： 3-CNF 求解中只有一个变量值确定的动态块可以产生多解。若设定关联变量值后的剩余动态块仍然有多值可设，则可连续查找关联动态块，直至无解、有惟一解或有关联段的结束动态块出现。如果最终出现动态块无解，则关联段无解。如果出现动态块有唯一解，可反方向设定关联变量值去确定前面每个多值动态块的解；如果多解情况最终关联的是未曾设定解的子句块，可以把子句块解设定，然后反方向去确定多解的动态子句块，最终会连成一个关联段，得到关联段的解或无解。 6. 3-SAT 分段求解方法 3-SAT 的子句块有解，并且关联段有解，那么 3-CNF=1 才会有解。依据这一原理，我们先检查子句块是否都有解。如果子句块都有解，那么选择 3-SAT 的关联段，求出各关联段解，进而能够组合求出 3-SAT 的满足解。 6.1 关联段子句消去法表格式 3-CNF=1 求解算法如下：（ 1 ）选择左侧子句块为起始块；判断有块解后选择一个块解，无块解 3-CNF=1 无解。（ 2 ）消去至少含有一个与这个块变量相同且值相同的所有子句。（ 3 ）向右寻找靠近的 2 个变量值已确定的动态块，设定最后一个变量值，将含有该变量且值相同的子句块消去；若设定 0 或 1 都不能够消去动态块全部子句，则知从起始块设定值开始得不到 3-CNF=1 的解，需要选择下一个起始块解进行从新操作；若起始块解都操作过并无解，则 3-CNF=1 无解。（ 4 ）若是只有 1 个变量值已确定的动态块，则需要同时确定 2 个变量的值。此时应依据定理 4 先判断有无解；无解，则需重复下一个起始块解。（ 5 ）通过（ 4 ）判定有解，并依靠推论 4 判断出有唯一解，则设定 2 个变量值，并消去所有相关子句。（ 6 ）如果通过（ 5 ）得出设定 2 个变量值多解的情况，依据定理 5 向后去确定关联段的解。（ 7 ）如果（ 6 ）的操作的关联段一端遇到无后续关联的子句块，并且关联段无跨越子句块，则该关联段结束，可以进入下一个关联段求解操作；如有跨越关联子句，需通过跨越子句向左右两个方向求段解。（ 8 ）依据子句消去法，若所有的关联段都有解，那么 3-CNF=1 就有解。其解为各关联段解的顺序组合。由于 3-CNF 一个关联段最多有 7 个段解，所以 3-CNF=1 通过分段求解，如果每个关联段都有解，则可以配合出 3-CNF=1 的多组解。 6.2 子句消去法实例我们以图 2 的例子来说明子句消去法。（ 0 ）判断子句块中是否有子句数为 8 的，是， 3-SAT 无解。（ 1 ）最左面的 x1x2x3 子句块为起始块，此块只有 000 、 100 和 010 三个块解。选择 x1x2x3=010 ，消去有 x1=0 、 x2=1 、 x3=0 的所有子句（绿色部分是消去的子句）。图 2 逐步消去子句块求解过程（ 1 ）（ 2 ）向右，以子句块尾最靠左为原则，寻找剩余子句块。此例为块尾是 x5 的子句块。由于该块有 x3=0 ，只有 x4x5 关联的动态块出现｛ 00 、 10 、 11 ｝，有唯一动态块解 010 ，于是选 x4x5=10 消去相关子句。剩下以 x6 关联的动态块只需要设定 x6=0 就可以将该动态块消去，选择 x6=0 ，并消去相关子句（见图 3 ）。图 3 逐步消去子句块求解过程（ 2 ）（ 3 ）剩余没有 x7 结尾的动态块，只二变量确定块尾为 x8 的动态块，设 x8=0 ，消去 x8=0 相关子句后，遇到了需要设置 x7x13= ｛ 10 、 01 ｝多解的动态块解（见图 4 青色块）。图 4 逐步消去子句块求解过程（ 3 ）（ 4 ）在关联段中遇到动态块多值，为了避免选择关联段无解的分支，我们采用向下寻找唯一解的方法来保证关联块有解。此时暂不设置变量值，而是通过与其一元相关子句块连续寻找有唯一解的子句块。向上关联有 x5x13x18 子句块，向下有 x6x13x21 子句块和 x13x14x16 子句块。它们后续关联的都是需要三个变量设值的子句块。可以假定这些子句块是新的一个关联段，照顾到与前面关联关系，可设定子句块解，往回消去前面没有定解的动态块（见图 5 青色所示）。图 5 逐步消去子句块求解过程（ 4 ）（ 5 ）由于 x13x14x16 子句块是无后续关联的，可以设定 x13x14x16=001 消去相关子句（见图 6 ）。图 6 逐步消去子句块求解过程（ 5 ）（ 6 ）动态子句块 x7x8x13 已有 2 个变量值被确定，必需设 x7=1 将其消去。然后将 x11x12x14 和 x9x10x11 的子句块消去（见图 7 ）图 7 逐步消去子句块求解过程（ 6 ）（ 7 ）此时， x8x13x18 动态块必需设 x18=0 。接续消去 x18x19x20 的子句块及关联子句块（图8 ）。图 8 逐步消去子句块求解过程（7）如图8 所示，至此就得到了这个 3-CNF=1 的一组解。由图8 我们看到通过以上消去子句操作，已经没有了剩余子句。从表下面一行就得到了这个 3-SAT 的满足解。解的变量空白处，实际上是值为 0 和 1 两种情况，这表明实际上所求出的解是一组，解的数量应是 2 的空格数指数倍。本例求得的合取范式一组解包括 2 3 个解。此例全部子句在一个关联段中，如果 3-SAT 含有多个独立的关联段，那么将段解组合在一起就是求得的 3-SAT 满足解。如果想要求出 3-SAT 更多的解，必需将起始块解都考虑到，这样才能达到目的。此例题其它两个起始块解都不能够形成段解，因而通过它们不可能有 3-SAT 的解。 6.3 关联段解处理讨论 3-SAT 的满足解是由 n 个变量值组成的，其中任何一部分变量值不构成解的变量值， 3-SAT 就无解。这种局部特征是破解 3-SAT 难题的关键。依据定理 4 ，只要 3-SAT 子句块都有解，那么一元关联段总可以判断出是否有解。二元关联段是否有解很容易判断。判断一元确定的动态块有几个解，要看其余子句变量的状况。如果要确定的变量值为｛ 00 、 01 、 10 ｝｛ 11 、 01 、 10 ｝｛ 11 、 01 、 00 ｝｛ 11 、 00 、 10 ｝之一，则有一个解；为｛ 00 、 01 、 10 、 11 ｝无解；而为｛ 00 ｝｛ 11 ｝｛ 10 ｝｛ 01 ｝｛ 10 、 01 ｝｛ 00 、 11 ｝之一，则有多个解。这种多解可以在一个变量值被确定的情况下，仍然可能选择另一个变量值将剩余子句块消去。如果动态块有多个解，为了后续动态块不出现无解，可以依据动态块多解向后查找定解，然后反向确定动态块多解，不需要将所有的可能解都计算一遍，只要能够得到关联段解就达到了求 3-SAT 解的目的。要求出更多解，需要将每个关联段的段解都求出来进行组合。下面例子是对一个关联段求解的过程。图 8 的起始段只有 000 、 100 和 010 这 3 个块解，求解只要从这 3 个值出发就可以。图 8 （ 1 ）出现二元判断无解的情况。图 8 （ 2 ）出现一元判断无解的情况。图 8 （ 3 ）才是有段解的情况。图 9 有段解的判断关联段结束在两个相互独立的子句块之间。由于没有恒一子句的 3-SAT 子句数量不超过 2 3 C n 3 个，并且相关子句越多， 3-SAT 的解越少。因而子句数量越接近 2 3 C n 3 个，那么分段子句消去法的效率越高。每一个关联段就是一个 3-SAT ，因而 3-SAT 并不完全是一个全局性的问题。 7. 3-SAT 分段子句消去法时间复杂度 3-CNF=1 的解是由 n 个变量值组成的，如果其中任何一部分变量值不构成解的变量值，那么 3-CNF=1 就无解。分段子句消去法，将 3-CNF 的子句分成了相互关联的段，并以段解来组成 3-CNF=1 的解。由于关联段是不重复的，所以 3-CNF 的关联段最多有个，此时最多有一至两个子句块之间关联，其余子句块都是独立的。由于 3-CNF 的每个关联段不会超过 7 次求段解操作得出段解，因而用分段子句消去法求出 3-CNF=1 的解或判定无解，最多需要进行 7 次消去子句的过程。从这一点来说，用分段子句消去法求 3-CNF=1 的解是一个 O( n ) 时间复杂度的算法。其实， 3-CNF=1 是否有解，主要取决于子句数 m 和子句分配的结构，亦即子句之间关联的程度。 3-CNF 关联段子句越多， 3-CNF=1 的解就越少，反之解的数量会很多。当所有子句块只有一个子句并且都是独立块时， 3-CNF=1 会有最多的解。 8. 结论 3-SAT 求满足解的分段子句消去法是一个多项式时间复杂度的算法。本算法证明了典型的 NP-complete 问题之一 3-SAT 是一个 P 类问题。依据学术界公认的观点，分段子句消去法可以说明 P=NP 。联系邮箱： accsys@126.com Accsysuibe@uibe.edu.cn 2015-09-19 备注：从 C n 3 个子句块中选块解，如同做除法试商。修改于 2015-10-04; 个人分类: 科研论文|5536 次阅读|2 个评论

再请杜立智详细解析姜咏江解决了3SAT难题如何？: 热度 3 accsys 2015-9-22 04:03; 再请杜立智详细解析姜咏江解决了 3SAT 难题如何？科学网上的牛人杜立智还是很有影响力的。一篇博文《详细解析天才的姜咏江解决了3SAT难题》至今已有1017次阅读，20次评论，很好。我以讨论的心态从事科学研究，目的是能够从批评中得到启发。杜老师的轻蔑带有讽刺意味的解析评论，是激发我前进的动力。所以我感谢杜立智。还是被杜老师认为是脑残的“子句消去法”，有了独特的感觉，更需要象杜立智这样的功底深厚的人批评。博文地址： http://blog.sciencenet.cn/blog-340399-928224.html 姜咏江 2015-9-22 附录：杜立智博文和一些评论详细解析天才的姜咏江解决了3SAT难题各位，70余岁高龄的姜咏江博主，名校计算机专业退休老教师，一次又一次地声称解决了世界难题。蒙他看得起，多次点名要求我予以评判。我已经多次评论过，他的那一套荒谬可笑，他还要继续，并还要点名要我评。我就恭敬不如从命了，反正他的天才解决方案，我稍稍一看，立即看懂，所以也不花什么时间精力。我这里表这个态：看算法的论文关键是必须进入思路，哪怕别人表达不太好，推敲一下很快进入思路就能看懂。对于这个世界任何高档次高难度的算法论文，只要不涉及其他领域专门的知识，主要是复杂的思路和基础数学，我都能很快进入思路很快看懂，并能很快确定算法到底难不难，有多高的价值，作者实力如何。两种语言，中文英文。而不像大量论文和基金评审专家猪，根本看不懂就做评论。下面是他最近声称解决了3SAT问题的方法，岂止3SAT，4，5，6SAT…等等他都解决了！一个逻辑多项式如果存在一项的值是 1 ，那么这个逻辑多项式的值一定就是 1 。同样，一个逻辑项的存在为 0 的因子，那么这个逻辑项的值一定是 0 。逻辑变量非的值，一定是逻辑变量值的反码。逻辑运算的这些基本规律是子句消去法计数成立的基础。本文用“ + ”表示或运算，用“ ’ ”表示非运算，与运算符号省略。我们可以利用逐次消去 n 个变量或其非运算一方，通过 n 次消去，最终确定消去的变量取值是否是合取范式值为 1 的解。这叫子句消去法。用子句消去法进行改造，获得了下面的子句消去计数法。用子句消去计数法求解 k-CNF-SAT 问题算法如下：（ 0 ）设立 n 元单侧计数器： x 1 ’x 2 ’x 3 ’…x n-1 ’ x n ’ ,…, x 1 x 2 x 3 …x n-1 x n ,x 1 ’x 2 ’x 3 ’…x 5 ’x 6 ，共计 64 个。（ 1 ）去掉恒一子句 ( x 1 + x 1 '+ x 2 ') ，剩 ( x 2 + x 3 + x 4 )( x 1 '+ x 3 '+ x 4 ')( x 1 '+ x 2 + x 5 ')( x 2 + x 3 + x 6 )( x 1 + x 5 + x 6 ') （ 2 ）剩下非恒一合取范式的第一子句使含 x 2 x 3 x 4 标识的计数器都加 1 ；第二子句使含 x 1 ' x 3 ' x 4 ' 标识的计数器都加 1 ；继续 5 次，查遍所有子句。（ 3 ）令为 0 计数器的变量取反码值即得解。例如，计数器 x 1 ’x 2 ’x 3 x 4 ’x 5 ’x 6 ，于是得 f ( x 1 ,..., x 6 ) 值为 1 的解有：（ 110110 ）。（ 4 ）一次性可以写出所有解。互为反码标识的计数器都为 0 ，则对应逻辑变量组合双方都是解。验证：对于所得解可以带入原式验证。将 x 1 =1 、 x 2 =1 、 x 3 =0 、 x 4 =1 、 x 5 =1 、 x 6 =0 带入原式得： f (1,1,0,1,1,0)=1 。 3. 概念与性质为什么子句消去计数法就能够求出 k-CNF=1 的解？它的证明就在下面的概念和方法中。定义 1 ：如果子句中同时有逻辑变量和其反表示，则称子句为恒一子句。显然，恒一子句的值总是 1 ，与逻辑变量的取值无关。定义 2 ：所有包含变量 x 的非恒一子句叫 x 相关子句。定义 3 ：我们将 n 对互反变量只取变量或变量非，得到的 n 个变量组合，叫一侧。显然， n 个变量的一侧有 2 n 个。子句消去计数法的计数器就是记录一侧含有的子句数量的。定理1 ： n 个变量合取范式 k-CNF 中一侧相关子句数最多为C n k 。证明：因为一侧只有 n 个变量，从中取出 k 个为C n k 。此定理可以用来检查给定的合取范式是否不正确。如果给出的合取范式的一侧相关子句超过这个数，则可判定合取范式有错误。定义 4 ：将合取范式一个变量的值定为 1 的子句消去求解的方法，称为子句消去法。显然，子句消去法经过 n 次消去，若没有剩余子句，则 k-CNF 是可满足的，反之不满足。定理2 ：非恒一子句全体，消去 x 相关子句中，一定不含有其反变量 x’ 。证明：因为非恒一子句 x 与 x’ 是不同时出现在一个子句，所以消去 x 相关子句， x’ 相关子句依然存在。完全定理： n 个逻辑变量所成的 k 元合取范式 k-CNF ，最多有C 2n k 个子句。非恒一子句最多有个。证明：因为每个子句的元素可以是逻辑变量或它的非，这相当从 2n 个元素中取出 k 个的组合数，即为。而恒一子句最多有个，所以非恒一子句最多有个。推论：完全合取范式的值恒为 0 。因为完全合取范式包含 x 与 x’ 的所有相关子句。所以用子句消去法无论经过怎样的 n 次消去子句，都不能使剩余没有子句。可满足定理：若非恒一子句中互反变量有一侧相关子句不存在，则 k-CNF-SAT 可满足。证明：因为 x 的相关子句全体包含一侧所有的 n 个变量或其非，如果一侧不存在，则可确定其相反一侧变量逐一消去，依据定理 2 可知最终没有剩余子句。满足定理是我们进行 k-CNF-SAT 求解子句消去计数算法正确性的依据。步数定理：用子句消去计数法确定 k-CNF 可满足全部解，最多用了C 2n k 次检查。因为子句数不超过C 2n k ,得证。步数定理告诉我们，上面介绍的求解算法是一个多项式时间算法。各位，包括计算机专业的专家们，包括计算机专业的一大部分基金评审专家猪，你们是否能立即看懂了？我断言，大比例这样的人会半天看不懂！首先一个问题，他的方法对吗？我告诉你们，他的方法毫无疑问是对的！那么，姜博主真的是天才了？这么顶级的世界难题他一下子就解决了，甚至仅仅只是“回去想了想”？姜博主的整个工作，相当于是在解这样一个方程x=x，一样的无聊。尽管如此，我还是佩服姜老师的智商，一个70余岁的老人，他玩的一些花样，大量计算机专业高职称高学历的垃圾一点头脑的人是看不懂的。记得有这样一个谜语：七七四十九，和尚庙里有。他洋洋洒洒这么长的一段所谓“算法和证明”，其实只要一句话就可以概括。我就不概括了。这就是姜老师解决世界难题的方法。联想到上一次他声称解决了整数子集和问题，他那个方法和程序若是自己独立完成的，表明他的头脑没有衰退，智商很高。因为我判断大量杂牌一点头脑的计算机专业的人是做不出来的。部分网友的评论：; 个人分类: 随笔|2926 次阅读|4 个评论

我终于找到了子句消去计数法分组定解的多项式时间算法！: 热度 1 accsys 2015-8-30 08:36; 经过努力，终于在分组定解的基础上，利用可能解表，用逐步扩展定解的方式，取得了获得3SAT解的多项式时间算法。为了庆祝一下我艰苦努力的成功，特发此文自己祝贺一下！这也是为了纪念。 2015－8－30; 个人分类: 随笔|2225 次阅读|1 个评论

详细解答3CNF求解运算器: accsys 2015-7-23 08:16; 详细解答 3CNF 求解运算器姜咏江为了介绍我的子句消去计数法（见 http://blog.sciencenet.cn/blog-340399-905817.html ）如何能够快速求出 k-CNF-SAT 的全部解，我在博文《 3 － CNF 一秒钟求出解》中给出了求解运算器时序仿真截图。这张图包括 P/NP 专业人士也多有不解之处，提出了多长时间能够得出结果的疑问。为了能够解释诸多疑惑，我有必要对求解运算器时序仿真图进行详细一点的解释，并增加一个求解实例，通过实例说明子句消去计数法是一个快速解题算法。例1 ，求下面合取范式的满足解。 (x1’+x2’+x3’)(x3+x4+x5’)(x2+x4’+x5)(x1’+x2’+x3)(x2’+x3’+x4)(x1’+x4’+x5)(x1+x3+x5’) (x1’+x2+x3)(x1+x3’+x4’)(x1’+x2+x4)(x1’x3+x4’)(x1’+x4+x5)(x2’+x3’+x5)(x2’+x4’+x5) (x2’+x3+x5)(x1+x2’+x3’)(x1+x2’+x4)(x3+x4+x5). 该运算器求解结果如下图 1 ，懂得了我的子句消去计数法，你立即就可以看出解是多少了。图 1 具有唯一解为了能够让您迅速看懂这张仿真图，我先要介绍一下图中各部分的意义。最左侧一栏是输入输出标志栏，箭头中的 i 或 o 分别表示输入子句或输出标识。 Name 一栏是可选的非恒一子句，由于软件中不允许撇号做名称符号，故而将非运算符用下划线替代。例如“ _x2_x3x 5 ” 表示的是 x2’x3’x5 。再右面的一大宽栏是输入输出栏。上面横向有以纳秒为单位的计时，图 1 中仿真的时间在 30 纳秒到 110 纳秒之间。逻辑变量值为 0 ，用下细实线表示，值为 1 ，用上实线表示。如果是逻辑向量，可以直接用多位二进制数表示。变量 c 是 32 位的向量，故用 32 位二进制数表示。可能有的专家已经发现，所谓一侧计数器的名称正好与全体二进制限位数（一定位数的用数码 0 或 1 占位写出的数）一一对应。而在子句消去记数法中，有解存在，正好是那些值为 0 的计数器名称的反码。这样求解的过程中，只要找到值为 0 的计数器，就可以得到合取范式的解了！为此，我设计了每个一侧计数器为 1 标识（当然也可以设计成为 0 标识），并将全体为 1 标识组成一个向量。图 1 中最下面的输出变量 c 是 32 个一侧计数器的非零标志线组成的向量，从右到左，分别表示一侧计数器 0 号至 31 号不为 0 标志。如果某位置是 1 ，即表示该位置编号的计数器不为零；如果为 0 的，就表示该计数器的值是 0 。例 1 给出的合取范式用子句消去计数法，进行求解，只有 2 号计数器值仍然是 0 。 2 号计数器的名称是 x5'x4'x3'x2x1' ，于是依子句消去计数法，此合取范式有惟一解 x5=1,x4=1,x3=1,x2=0,x1=1 。子句消去计数法运算器用多长时间可以求出合取范式满足解？从图 1 我们可以看到只要通过器件的 20 纳秒延时之后，就可以得到合取范式的解，也就是在我使用的微电子设计器件中，不超过 30 纳秒就可以得到全部解了！为增加感性认识我们再给一个例子及截图，看看如何一次性求出全部解。例2 ，有合取范式如下，求出全部解。 (x1’+x2’+x3’) (x2+x4’+x5)(x1’+x2’+x3) (x1’+x4’+x5)(x1+x3+x5’) (x1’+x2+x3) (x1+x3’+x4’)(x1’+x2+x4)(x1’x3+x4’)(x1’+x4+x5)(x2’+x3’+x5)(x2’+x4’+x5) (x2’+x3+x5)(x1+x2’+x3’)(x1+x2’+x4) 图 2 多解截图有解： x5=1,x4=1,x3=1,x2=0,x1=1 第 11 号计数器值为 0 ，名称是 x5’x4x3’x2x1 ，故有解 x5=1,x4=0,x3=1,x2=0,x1=0 第 27 号计数器值为 0 ，名称是 x5x4x3’x2x1 ，故有解 x5=0,x4=0,x3=1,x2=0,x1=0 第 31 号计数器值为 0 ，名称是 x5x4x3x2x1 ，故有解 x5=0,x4=0,x3=0,x2=0,x1=0 我们可以验证，这四组值都是例 2 合取范式的满足解。特别声名：合取范式运算器是本人独创，一切用本方法设计合取范式运算器形成的市场行为，必须经本人同意。 2015-7-23 转： http://blog.sciencenet.cn/blog-340399-928224.html; 个人分类: 科研讨论|4137 次阅读|0 个评论

3-SAT-CNF 一次性确定解！库克的P/NPC到头了！: 热度 2 accsys 2015-7-11 17:02; 3 － SAT-CNF 一次性确定解！姜咏江经过 n 次为逻辑变量赋值，就可以找到 n 个变量的 3-SAT-CNF 的解，有人做得到吗？本人用我的论文 http://blog.sciencenet.cn/blog-340399-902729.html 中介绍的子句消去法，就可以在 n 次子句消去之后，确定出 n 个变量的 3-SAT-CNF 的解。这大概不会有人相信！等着，我会告诉大家这一切是如何做到的。如果你有兴趣，就写几个 3 元合取范式给我解。不过现在还是手工操作，变量不要超过 5 个行吗？ 2015-7-11; 个人分类: 科研论文|4030 次阅读|4 个评论

非常复杂问题一旦引入新算法就变得十分简单了: accsys 2015-7-8 17:22; 非常复杂问题一旦引入新算法就变得十分简单了姜咏江在数学史上，复杂问题一旦引入新方法后，问题求解就变得十分简单了，这样的例子很多。例如从加减法运算引入乘除法运算，引入矩阵运算等。 K-CNF-SAT 问题以前求解相当复杂，常常通过已有的方法不能达到准确地求解，于是人们想到近似计算，概率引入的计算等，弄得十分复杂，甚至将计算者自己都绕了进去。姜咏江创造的子句消去法是一种全新的求解 K-CNF-SAT 问题的方法。这种方法使本来 3SAT 求解十分困难的状态，一下子变得十分容易起来。这就是在数学计算中引入新的计算方法的魅力所在。子句消去法与传统的数学精准的概念不同，不是对众多的变量一个个地讨论变化的相互影响，而是抓住子句的主要变量，一次性地将主要变量存在的子句全部处理掉。这看起来操作十分简单的事情，背后隐藏着对逻辑电路抽象的深刻理解，对数学概念和方法的准确把握，透过数学运算的现象，看出其深刻的本质才行。不然，近 50 年为何没有人发现这一简单的合取范式求值方法？子句消去法并不是将变量一个个地去掉了，而是在消去子句的同时，变量又会以另外的身份出现，我们怎么能够想得到呢！一个新的计算方法如果不能够使原本复杂的求解问题简单化，那么这种新的算法就失去了它存在的意义。有的网友看到子句消去法使 K-CNF-SAT 问题的求解变得如此简单，如此初等，说什么也不相信解决世界级的数学难题，竟然会如此简单！其实，不管有多少人不相信，科学的方法终究是科学的方法。计算 K-CNF-SAT 问题的解，居然象求多元一次方程那么简单，只要解题者设定一些前面变量的值，那么后面的变量会一个跟着一个被确定出来，似乎真有些不可思议了。然而事实摆在那里，不容你不信。由于 SAT 问题涉及到密码学、遗传学、数理逻辑、人工智能、机器学习、 VLSI 集成电路设计与检测、数据检索等方面都有重要的应用，所以慎重地对待子句消去法，这是科学发展的正常理念。解决的办法就是让理论的创新应用于实践，让应用者利用子句消去法解决那些实际当中的问题，在实践中检验它的正确性，必然是其发展的正确途径。新的数学计算方法的引入，一定是全新的理论研究的开始。 2015-7-8; 个人分类: 科研讨论|2043 次阅读|0 个评论

回复网友汪小龙的友情提醒: 热度 1 accsys 2015-7-6 14:06; 回复网友汪小龙的友情提醒姜咏江汪小龙 2015-7-6 11:22 博主回复(2015-7-5 21:04)：我已在Quartus II上设计电路测试过，解法定理没有问题。 ============================================ 对于小的算例有效，不能说明对所有的k-SAT都有效。一般的算例都是容易解的，有些k-SAT是特别难解的。有人从理论上证明过，3-SAT在子句与变量数目比值在4-5之间的某个值会发生相变，出现特别难解的算例。找到这些算例本身就很难。在SAT competition网站有很多很难得算例，如果你的算法能极快地攻克他们，去参加SAT competition，就能很快得到国际承认。关于 3-CNF-SAT 我将文中的例题到 EDA 软件 Quartus II 设计成电路，还对6个变量下全部子句的2-CNF也同时测试了一下。同我在证明文中的结论一样。图 1 不完全 3-cnf 和完全 2-cnf 测试针对网友提出的问题我回答如下： 1. 理论上能够解决的问题，应该对任何算例都适用，不会有特例。 2. 你说的值会发生变化不知是指什么？还要说清楚的问题是 n 个变量的 k-CNF 的子句数最多是 C 2n k 个。这样子句最多的 k-CNF ，我们可以称之为完全合取范式。如果 k=3 ，那么 3-CNF 最多有 2n(2n-1)(2n-2)/3! 而已，如果某所谓 3-CNF 的子句多于这个数，那么其中必有重复的子句。这种重复的子句不应该存在。 3. “ 有人从理论上证明过，3-SAT在子句与变量数目比值在4-5之间的某个值会发生相变，出现特别难解的算例。” 我敢说这个人肯定没有注意到 k ≤ 2n ，而子句总数不能超过 C 2n k 个这样的事情，因而他犯了重复出现子句的错误。 4. k ≤ 2n ，子句数为 C 2n k 个的 k-CNF 的值一定为 0 。将这句话做为定理，证起来也十分容易。因为子句为 C 2n k 个的 k-CNF 中若有 k 个变量或者非的子句，则一定有对应的反子句。例如 C 2n 3 个子句的 3-CNF 中，有 x4’+x7+x9’ 子句，则必有 x4+x7’+x9 子句在其中，它们是互反子句。所以无论如何， C 2n 3 个子句的 3-CNF=0 。最后要说的是 k-CNF-SAT 成立是有条件的，对一个确定的 k-CNF 来说， n 个逻辑变量的某些值是 k-CNF-SAT 成立的，而也有某些值使之不成立。这一点从图 1 就可以看到。透彻的理论研究，不必将所有人的观点都照顾到，也不必一一拜读，只要方法和论证都正确，倒应该让那些似是而非的说法回归到正确的理论论证上来。抱歉，现在我相信国内能够有人理解，不忙用蹩脚的英文讨论。因为直接回复许多表示做不到，因而另独写文。 2015-7-6; 个人分类: 科研讨论|2473 次阅读|2 个评论

我已从根本上击破3SAT问题: 热度 5 dulizhi95 2011-9-1 20:49; 我已从根本上击破 3SAT 问题所谓从根本上击破，就是我的程序在多项式时间内能轻松计算任何 3SAT 算式。在 PC 机上计算几百个子式的 3SAT 问题易于反掌。同样，在PC机上，我的程序能轻松计算几万个节点的Hamilton环问题。正确率均为百分之百，至少迄今我找不到我算不出的反例。全世界有多少英才专家倾毕生精力研究3SAT，最终也就能计算不到100个变量。为避免遭致反对或质疑，发这类博文还是严谨一些吧。以后未经权威认可的东东，我不以自己的认识为依据在这里表述。所以，不谈NP，只谈我的程序能计算什么，这是非常具体现实，立马可以验证的。我的目的是：希望得到交流或帮助的机会，尽管可能性不一定大，但迄今，网上网下依然得到了一些有益的建议和帮助，在此致以深谢！; 7142 次阅读|4 个评论

证明不可满足: 热度 3 haijunzhouitp 2011-5-5 17:16; 3-SAT问题很简单，表达起来。3-SAT问题可以很难，尤其是想证明一个公式不可能满足的话。说起来容易，做起来难啊。希望能够用随机搜索的方法，对一个特定的3-SAT公式，找到一些该公式不可能满足的证据。如果能够对约束密度为常数的随机3-SAT公式有好的效果，那将很有趣。 2011年5月5日，赫尔辛基终于将第一篇论文贴到arXiv上去了： “ Witness of unsatisfiability for a random 3-satisfiability formula”, Lu-Lu Wu, Hai-Jun Zhou, Mikko Alava, Erik Aurell and Pekka Orponen (arXiv:1303.2413, 2013) http://arxiv.org/abs/1303.2413 ...2013年3月11日，香港; 个人分类: 有所思|3738 次阅读|4 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 3SAT

相关帖子

相关日志

关闭安全验证