博文
全部博文|未分类|
生活点滴|
计算机核|
随笔|
教学点滴|
科技畅想|
计算机实验|
教学笔记|
计算机科普|
科研讨论|
机器计算|
国防科研|
科研论文|
3SAT解法|
k-SAT求解|
SAT问题|
P/NP问题|
子句消去法|
数学定义|
相关计算|
离散数学|
科研生活|
类脑计算|
计算机制造|
限位数|
数字密码锁|
仿量子计算机|
- SAT问题满足解详解求解例题
- SAT问题满足解详解求解例题 姜咏江 从一开始接触 SAT 问题求解，我就说过：“科学网是我科研的地方。”两年，我在科学网上经历了与别人不一样的研究历程，当然，也收获了与别人不一样的成果。我以 3-SAT 问题求解的实例，来详细告诉感兴趣的人们，如何在多项式时间内求出这类 SAT 问题满足解。这是对以往阅读过我那 ...
- SAT问题去重复子句的时间复杂度是怎样算出来的？
- 姜咏江 SAT 的定义中是不允许出现重复子句的，但在子句消去的过程中，会出现降阶的子句块中有重复的子句。 t 阶子句块变量唯一解是因为它有 2 t-1 个相同的表现值（ 1 ≤ t ≤ k ）。在消去子句的过程中很难事前知道那些子句会重复，这样证明消去重复子句这一步算法时间复杂度为多项式时间就很困难。不过我们 ...
- 子句消去法求SAT问题满足解口诀
- 姜咏江 消去块中唯一解， 不然找一可选解， 解多暂时一边放， 全多选解可得解。 《时间复杂度解释： 子句块变量唯一解的判断条件为有2 k-1 个0或1，如果同时0和1都有2 k-1 个SAT无解 。 SAT 的子句块最多有 2 k C n k +2 k-1 C n k-2 +…+ C n 1 这多项式个，子句块变量最多 ...
- 子句消去法或者可以解释物种消亡的密码
- 热度 1
- 姜咏江 按照生物学基因的理论，生物种群的基因构成了 n 元合取范式 n-CNF 。如果用数码 0 和 1 来表示基因的变化，种群的基因编码就构成了一张超庞大的表。这张表正是本人研究 k-SAT 问题，即当 k=n 时的求满足解的分析表，此时的分析表已经退缩成了 n 元变量的子句块。 在子句消去法中，子句块形 ...
- 3-SAT快速求解方法
- 姜咏江 SAT问题中最基本的是3-SAT。子句消去法可以在多项式时间完成对3-SAT求出满足解，但如何对具体的3-SAT求解达到最快？ 依据子句消去法确定变量唯一解的基本规则，只要在k阶子句块中一个变量有2 k-1 个相同的表现值，那么这个表现值就是这个变量的解。3-SAT的子句块最高是3阶，在消去子句的过程中会剩下 ...
- 公开搞学术研究要经得起冷嘲热讽
- 姜咏江 学术研究并不都需要秘密地进行，特别是那些所谓的世界难题一类，公开在科学网上研究论证，不怕讥笑和嘲讽，借助于批评者，能够获得快意和驱动力，激奋你快速前进。这是我两年多钻研子句消去法求解 SAT 问题满足解的特有体会。 两年中，我从无知 SAT 问题到有所收获，除了我自身的数学和计算机的功底之外 ...
- 韩春雨事件如何结局？丢人现眼的中国科学评价体系
- 热度 25
- 韩春雨小辈搞了一个世界性难题，对如何评价这个“三无人员”的成果，却成了中国科学评价体系的重大危机。13位大腕联名否认，更有甚者，发文到该期刊，要求撤销韩氏论文。实在是中国科学界丢人现眼的大事件！ 中国的学术权威实在是气势宏大，要韩春雨自证清白，还要组织重量级人物监督。我是 ...
- 考虑科学尽快发展应设立国家级科学协作奖
- 热度 2
- 早年间听到一个流传在国内的笑谈，据说是国外被参观科学技术单位有说法，”多个日本人或一个中国人来参观要注意，你的科学技术会被学去；多个中国人来参观或一个日本人来参观，就不必在意了。“ 虽说是笑谈，但反映了中日两个国家科学研究风格的不同。为了国家创新发展，产生更多的科技原创 ...
- 也谈什么是数学
- 热度 2
- 什么是数学？这个问题需要从数学的起源挖掘，而不能从现今的各种数学方法中去找答案。 不可否认，数源自事物的比较。最简单的比较是是与非的问题。这是最基本的比较，其结果现在由逻辑值来表示。有比较才会产生推理，因而比较是逻辑学的基石。 比较只能在事物的同种属性中进行 ...
- 论子句消去算法的多项式时间复杂度
- 论 子句消去算法的 多项式时间复杂度 姜咏江 （对外经济贸易大学 北京 中国 100013 ） 2016-10-30 摘要 本文重点论证 SAT 问题算法时间复杂度问题。文中给出了运用子句消去法求 SAT 满足解的基本方法，并对该算法的每 ...
