科学网

 找回密码
  注册
搜索
热搜: 科学 论文
搜索
这么大的问题国内外专家不可能轻易认可你
热度 2 姜咏江 2017-8-23 06:29
这么大的问题国内外专家不可能轻易认可你 姜咏江 P/NP 这个世界难题不知道耗费了多少人的精力。完成这个难题,需要研究人员精通数学和计算机两方面理论和方法,实属不易。 出于兴趣所致,我也钻进了这个圈子。用了三年多的时间,终于将这个问题中的 SAT 问题的多项式时间算法(子句消去法)研制出来了。能否 ...
个人分类: 3SAT解法|2704 次阅读|2 个评论 热度 2
SAT问题的子句消去法及数学原理
热度 2 姜咏江 2017-8-14 06:41
SAT问题的子句消去法及数学原理 姜咏江 对外经济贸易大学 ( UIBE) 摘要 本文我们介绍如何利用限位数理论,通过子句消去法算法( CEASP),在O(n k+1 )多项式算法时间复杂度来求解SAT问题满足解。SAT问题可以用二进制数码以表的形式表达出来。我们借助于限位数理论文中定义变量唯一解和 ...
个人分类: 3SAT解法|3857 次阅读|4 个评论 热度 2
用C++编写的子句消去法要比VFP快得多
姜咏江 2017-8-10 12:44
用 C++ 编写的子句消去法要比 VFP 快得多 姜咏江 本人最近为解决巨量3-SAT问题,用C++编写了子句消去法程序。与以前用VFP所写程序执行比较,C++程序要快多了。一个实际逻辑电路转换的合取范式求满足解,VFP程序执行用时2秒,而用C++程序执行时间不到一秒。下图是对比。C++用负数表示“假”,用正数表示“真” ...
个人分类: 3SAT解法|2169 次阅读|1 个评论
Algorithm ZJXQF for SAT Problem
热度 1 姜咏江 2017-5-16 08:07
Algorithm ZJXQF for SAT Problem &n ...
个人分类: 3SAT解法|2147 次阅读|1 个评论 热度 1
3-SAT满足解软件ZJXQF使用说明书
姜咏江 2017-5-10 08:37
3-SAT 满足解软件ZJXQF使用说明书 姜咏江 2017-5-1 直到本人发明的《子句消去法》,没有人能够肯定自己设计出了在多项式时间求出 3-SAT 满足解的程序。 3-SAT 问 ...
个人分类: 3SAT解法|2414 次阅读|没有评论
科研需要坚韧不拔的意志和无所畏惧的精神
姜咏江 2017-5-1 22:20
姜咏江 有一段时间没写博文了,原因很简单,忙着将子句消去法写成计算机程序。说实在的,对一个七十多岁的人来说,还真是有点玩命。但我这个人办事不愿意半途而废。今天是“五一”劳动节,我确实还真地劳动了一番,将求 3-SAT 满足解的程序彻底完成了。高兴之余,想起来写点,以作为纪念。 为什么要拼命 ...
个人分类: 3SAT解法|2802 次阅读|没有评论
基于3SAT问题说明子句消去法的多项式时间复杂度
姜咏江 2016-12-8 08:44
基于 3SAT 问题说明子句消去法的多项式时间复杂度 姜咏江 为让大家能理解子句消去法的多项式时间复杂度特性,本文就以 3SAT 问题来简单说明。三个变量的子句在施行子句消去法的过程中,也会出现一个变量或两个变量的子句。因而 3SAT 问题实际就是最高阶是 3 的 SAT 问题。 算法 : ( 1 ) 子句消去法先查找 ...
个人分类: 3SAT解法|2148 次阅读|1 个评论
SAT问题满足解详解求解例题
姜咏江 2016-11-10 13:40
SAT问题满足解详解求解例题 姜咏江 从一开始接触 SAT 问题求解,我就说过:“科学网是我科研的地方。”两年,我在科学网上经历了与别人不一样的研究历程,当然,也收获了与别人不一样的成果。我以 3-SAT 问题求解的实例,来详细告诉感兴趣的人们,如何在多项式时间内求出这类 SAT 问题满足解。这是对以往阅读过我那 ...
个人分类: 3SAT解法|1861 次阅读|3 个评论
3-SAT问题中如何选择算法操作对象?
姜咏江 2016-7-2 07:41
3-SAT问题中如何选择算法操作对象? 姜咏江 计算机科学中的 3-SAT 问题之所以成为 NP 问题,是因为算法的操作对象选择变量造成的。将操作对象选择为子句,就会设计出多项式时间复杂度算法,从而就找到了 NP-complete 问题转化成 P 类问题的基本方法。 一年前我创造的“子句消去计数法”称为“子句标志消去法”更 ...
个人分类: 3SAT解法|2747 次阅读|没有评论
速度对比:一个可以快速求解的3SAT例题
热度 1 姜咏江 2016-6-4 16:39
速度对比: 一个可以快速求解的 3SAT 例题 姜咏江 表 1 是手工求解的结果,最快用了 8 分钟。 表 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 x1 x2 x3 x4 x5 ...
个人分类: 3SAT解法|2836 次阅读|1 个评论 热度 1

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-29 23:41

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部