科学网—标签

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

accsys 2016-10-20 09:12

这是我在研究子句消去法求3-SAT满足解的部分验证题，具体是否有解可以运用子句消去法检验一下，从这些题目中可以确认子句消去法的正确性。给出这些练习是为了减少朋友们的工作。 3SAT求解.xls 4sat4.xls 10Book2.xls 100.xls Boo2.xls Book1.xls Book2.xls Book3.xls Book4.xls Book5.xls Book8.xls Book9.xls two1.xls 二元关联.xls 全多解题.xls 一元关联2.xls

个人分类: 子句消去法|1985 次阅读|0 个评论

转基因计算不准确会产生意想不到的后果

热度 1 accsys 2016-7-8 08:51

转基因计算不准确会产生意想不到的后果姜咏江如火如荼开展的转基因工程用概率的方法进行计算，这会产生意想不到的后果。有概率知识的人都知道，小概率事件或迟或早总会发生。面对上万的基因组合形成的是数量庞大的 n-SAT 结构体。因为 n-SAT 找不到短时间能够计算出是否有满足解，就转而用近似计算的概率手段，一定会给基因重组等一系列生物工程带来巨大冒险。这种冒险毫无疑问会伤及我们人类本身。基因工程中出现的各种怪胎，已经明确地告诉我们，在没有准确的计算答案之前，就贸然开展关乎人类生存前途的转基因工作，极具危险。为此，研究准确的基因重组计算方法，是关乎人类前途命运的大问题。数学计算可以预测许多科学试验的结果，这正是数学的巨大作用。找到 n-SAT 的满足解或判断出无解的数学方法，一定会让转基因科研避开造成对人类的任何伤害。过去的实践已经表明，面对几万个基因的 n-SAT ，就是用超大型计算机也无法在人们能够容忍的时间内获得满足解，因而不得已才会有概率的近似方法被应用。这种问题的出现毫无疑问阻碍了包括转基因研究在内的科学研究的发展。 n-CNF=1 求解，即 n-SAT 问题就没有快速的多项式时间算法吗？本人创立的子句标志消去法是快速求出 n-CNF=1 解的有效方法（见前篇博文）。要求出全部解，我们可以将尽可能大的 n 位数做成一张表，用查表的方法去找到解或判断无解的数学方法还少吗？这种计算方法不久会制造出相应的运算器和计算机指令，这方面问题不赘述。其次，本人已经发明了能够依据部分基因变动判断n-CNF=1是否有满足解的快速算法。由于这种算法具有专利性，故暂不能公布。希望与基因工程研究的单位和团体协作。愿中国的基因工程研究能够走到世界的最前列。 2016-7-8

个人分类: k-SAT求解|1898 次阅读|1 个评论

k=n时k-SAT能快速求解吗？答田文洪老师

热度 1 accsys 2016-6-29 12:57

k=n 时 k-SAT 能快速求解吗？答田文洪老师田文洪 2016-6-2821:45 姜老师，一种情况就是如同SAT问题（可把3-SAT看作其特殊组合形式），当CNF输入项是2^k个不同项时，你所建议的方法的计算复杂度。此种情况可能是SA丅问题的最坏或最难情况，应该说明一下。博主回复(2016-6-2821:59) ：田老师，子句标志消去法基础在于反子句的概念。SAT是1到k个变量的子句都可能存在，都有反子句。只要n位二进制数可以由无反子句的子句或不在SAT中的子句构成，那么这个数就一定是SAT的解。上面是我与田老师的交流（见 http://blog.sciencenet.cn/blog-340399-987007.html ）。我的回复不会使田老师满意吧？也许答非所问。遵照田老师的建议，我需要很好地解答这方面的问题，这样能够一起更好地讨论。 1.k=n子句就是标志若k＝n，那么k-SAT中每个子句就是它的标志。因而只要看n位二进制数有哪些数不在k-SAT当中，取其反码则为解。特别是当子句数为2 n 个时，可以直接判定无解。这种情况应该说最简单，而不是最复杂。虽然k＝n时最多可有 2 n 个子句，但我们查找的是不在0～ 2 n -1中的数，这个过程的算法时间复杂度为O(x),x是一个变量。 2. 怎样理解 SAT 有n个变量的SAT，子句可以从1阶到n阶，因而各阶的子句总数会远远超过2 n ，但依子句消去法可知，低阶子句消去的同时，包含低阶子句的高阶子句也同时被削去了。由于低阶子句数总是高阶子句的组成部分，如果任何一低阶子句存在完全子句块，SAT都不会有解。不然从低向高阶施行子句标志消去的过程，剩下的子句标志都与剩下的n阶子句数有关。由1可知，其操作过程同k＝n时的复杂度相同。我们还是举例说明吧。例如，在下面的SAT中有2阶和3阶子句。当我们操作低阶子句消去子句标志时，高阶子句如果包含低阶子句，那么高阶子句的子句标志也同时被消去了，这样剩下的子句标志一定都是被消去子句的反子句或SAT中没有的子句构成的。于是知剩下的这些n位数的反码，一定是SAT的解。 … x4 x3 x2 x1 x0 　 NO 　 x4 x3 x2 x1 x0 1 0 0 　 0 0 0 0 0 0 0 1 　 0 0 0 0 1 　 0 0 0 　　　 2 　 0 0 0 1 0 　 1 0 0 　　　 3 　 0 0 0 1 1 　 1 0 1 　　　 4 　 0 0 1 0 0 　 1 1 1 　　　 5 　 0 0 1 0 1 　 0 　 0 1 　　 6 　 0 0 1 1 0 　 1 　 1 0 　　 7 　 0 0 1 1 1 　 1 1 　　 1 　 8 　 0 1 0 0 0 　 0 0 　　 0 　 9 　 0 1 0 0 1 　　 1 0 1 　　 10 　 0 1 0 1 0 　　 1 1 0 　　 11 　 0 1 0 1 1 　　 0 1 1 　　 12 　 0 1 1 0 0 　　 1 1 1 　　 13 　 0 1 1 0 1 　　 0 0 0 　　 14 　 0 1 1 1 0 　　　 0 1 0 　 15 　 0 1 1 1 1 　　　 1 0 0 　 16 　 1 0 0 0 0 　　　 1 1 0 　 17 　 1 0 0 0 1 　　　 0 0 1 　 18 　 1 0 0 1 0 　　　　　　　 19 　 1 0 0 1 1 　　　　　　　 20 　 1 0 1 0 0 　 21 　 1 0 1 0 1 AS.8' 1 0 1 1 1 　 22 　 1 0 1 1 0 AS.24' 0 0 1 1 1 　 23 　 1 0 1 1 1 　　　　　　　 24 　 1 1 0 0 0 　　　　　　　 25 　 1 1 0 0 1 　　　　　　　 26 　 1 1 0 1 0 　　　　　　　 27 　 1 1 0 1 1 　　　　　　　 28 　 1 1 1 0 0 　　　　　　　 29 　 1 1 1 0 1 　　　　　　　 30 　 1 1 1 1 0 　　　　　　　 31 　 1 1 1 1 1 是否正确，还请多多指正。姜咏江 2016-6-29

个人分类: k-SAT求解|3747 次阅读|2 个评论

解析网友姜咏江的“k-CNF-SAT子句消去法”

热度 2 liuyu2205 2015-7-24 23:38

网友姜咏江提出“k-CNF-SAT子句消去法”，认为其算法的时间复杂度是“多项式时间”，从而一举解决了K－SAT问题。我们认为其中存在双重错误，一方面，模糊了“多项式时间”的“立场”，将多项式时间解决的“一维数组的搜索问题”（P）混淆为“K（K=3）－SAT问题”（NP）；另一方面，将解决若干K－SAT问题实例混淆为解决K－SAT问题。所以，此“消去法”不过是演示了P＝P，并非“证明”P＝NP。为解析此“消去法”，我们将之与普通的“穷举法”进行对比，并借用一个3变元的2SAT的实例来说明之。一，网友姜咏江的“消去法” 用子句消去计数法求解k-CNF-SAT问题算法如下（见 http://blog.sciencenet.cn/blog-340399-905817.html ）：（0）设立n元单侧计数器：x1’x2’x3’…xn-1’xn’ ,…, x1x2x3…xn-1xn 001 x1’x2’x3 010 x1’x2x3’ 011 x1’x2x3 100 x1x2’x3’ 101 x1x2’x3 110 x1x2x3’ 111 x1x2x3 对每个子句，并将2个变量或变元的非都在某计数器中的计数器加1： (x1v x2) 000 x1’x2’x3’ 001 x1’x2’x3 010 x1’x2x3’ 011 x1’x2x3 100 x1x2’x3’ 101 x1x2’x3 110 x1x2x3’ 111 x1x2x3 (¬x2 v x3) 000 x1’x2’x3’ 001 x1’x2’x3 010 x1’x2x3’ 011 x1’x2x3 100 x1x2’x3’ 101 x1x2’x3 110 x1x2x3’ 111 x1x2x3 (¬x1v x3) 000 x1’x2’x3’ 001 x1’x2’x3 010 x1’x2x3’ 011 x1’x2x3 100 x1x2’x3’ 101 x1x2’x3 110 x1x2x3’ 111 x1x2x3 寻找计数器为0的计数器名称，以其每个变量表示的反码取值，得到的3位二进制数就是这个2-CNF-SAT的全部解：－000 x1’x2’x3’ 计数器真值000取反111，满足f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)。－010 x1’x2 x3’ 计数器真值010取反 101，满足f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)。－100 x1 x2’x3’ 计数器真值100取反 011，满足f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)。二，普通的“穷举法” 现在用普通的“穷举法”求解此实例，算法从3个变元的8个赋值出发，验证每个赋值是否能满足f： 000 x1’x2’x3’ f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(0)(1)(1)=0 001 x1’x2’x3 f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(0)(1)(1)=0 010 x1’x2x3’ f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(0)(1)=0 011 x1’x2x3 f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)=1 100 x1x2’x3’ f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(0)=0 101 x1x2’x3 f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)=1 110 x1x2x3’ f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(0)(1)=0 111 x1x2x3 f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)=1 同样可以得出f的三个解：－011 x1’x2x3 －101 x1x2’x3 －111 x1x2x3 三，解析网友姜咏江的“消去法” 由此可见，网友姜咏江的“消去法”实际上只是普通的“穷举法”，其“算法执行时间”＝c＊2^n，c是子句的个数。可以从二个不同的角度，解读“消去法”的“算法时间复杂度”： 1，若称“消去法”的时间复杂度是“多项式时间”：O（m），m＝2^n，那么，是相对于整个真值表而言的，换句话说，问题的规模是真值表的大小。在这种情况下，此“消去法”本质是在一维数组的真值表中搜索满足某性质的元素，而“一维数组的搜索问题”不过是一个普通的P问题而已，存在着“多项式时间”算法。 2，若称“消去法”的时间复杂度是“指数时间”：O（2^n），那么，是相对于K－SAT的合取范式而言的，问题的规模是n个变元，故此“消去法”可看作是求解若干KSAT实例的算法，但算法的时间复杂度是“指数时间”，而非“多项式时间”，故不能将此算法一般化为求解K－SAT问题。也就是说，网友姜咏江认为解决了P＝NP，不过是在演示P＝P，与真正的NP无涉。

个人分类: 不确定性问题和算法讨论|3575 次阅读|9 个评论

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

关闭安全验证

标签: K-SAT

相关帖子

相关日志

关闭 安全验证

标签: K-SAT

相关帖子

相关日志

关闭安全验证