点评《紐約客》科普“P versus NP”－流行的NP定义

柳渝 2016-8-11 12:00

－ 科学的每一部门都是对于整个自然界的一种描述，而这种描述通常都是近似性的。事实上，每件我们所知道的事都不外是对真理的一种近似叙述……我们现在学习的态度 ...

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

辨析“circle－free”与“halting” － 定性分析与定量分析

热度 2 柳渝 2016-8-7 12:44

在图灵1936年的论文中，我们看到了图灵并没有提出所谓的“停机”这个概念，而是一个至今仍然被人们忽视和误解的“circle－free”。这里，我们从认知的角度来进一步辨析“circle－free”与“停机”。 一般而言，认知事物有“定性、定量”之分，我们先追究一下“性、量”的汉字字源（汉字基因）： 性者，心生，人認 ...

个人分类: 不确定性问题和算法讨论|3741 次阅读|11 个评论 热度 2

关于“概念”的对话（2）

柳渝 2016-8-5 22:56

“概念”的认知是我们的“不确定性问题理论（NP理论）”的基本出发点之一。这里继续分享与网友wangbin6087关于“概念”的对话： wangbin6087: 概念的相对性是不言而喻的。它是对存在的定义性描述。不同的的层次和角度，就会有不同的表述。但从概念中，我们可以感受到表述者的境界。一切的争论都是出于对某一概念的执着。 ...

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

关于“概念”的对话（1）

热度 2 柳渝 2016-8-5 15:21

从博文：“问题”的系统观（整体观）（ http://blog.sciencenet.cn/blog-2322490-884042.html ）出发，与网友赵克勤针对“概念”进行了一系列的对话，这些对话散在几篇博文后面，这里把它们集中起来方便与大家分享： 赵克勤： 根据集对分析的思想，博主在这篇文章中就“问题”作了精彩的微观层次上的集对分析，例如从“ ...

2754 次阅读|3 个评论 热度 2

介绍一个求解SAT问题的程序SatZ（2）－k-SAT实例生成器

热度 1 柳渝 2016-8-2 20:21

SatZ（ http://blog.sciencenet.cn/blog-2322490-991076.html ）的作者提供了一个k-SAT实例生成器程序：gencnf+.c，为对SAT问题感兴趣的网友提供一个比较自己和他人工作的工具。 1. To compile under Linux or Unix : gcc gencnf+.c -O3 -o gencnf+ 2. To generate a set of (s2-s1+1) different k-sat instances of n ...

个人分类: 不确定性问题和算法讨论|3263 次阅读|1 个评论 热度 1

图灵1936年论文解读（3）：“不停机”的circle－free

热度 1 柳渝 2016-7-31 10:48

在图灵1936年论文第二章，图灵用circle-free来定义“可计算数（Computable sequences and numbers）”，这个定义实际上是由二部份构成的，首先由circle-free来定义“可计算序列”，进一步由“可计算序列”定义“可计算数”。 按照图灵的定义： A sequence is said to be computable if it can be computed by a circle-f ...

个人分类: 图灵论著专研与精译工作群|4760 次阅读|1 个评论 热度 1

图灵1936年论文解读（2）：可计算数

热度 1 柳渝 2016-7-26 12:20

图灵在1936年的论文（《论可计算数及其在判定问题上的应用》）的前言、第一、二章中提出了几个基本概念（见博文：可计算性——图灵1936年论文解读（1）），这些概念与当时数学和数理逻辑中一些观念不同，也与以前关于“算法”的直觉概念有别，图灵突出了机器计算的直观性，这些都是以后称之为“图灵机”的基础，这里我们先 ...

个人分类: 图灵论著专研与精译工作群|9088 次阅读|6 个评论 热度 1

NP理论（2）：“判定问题”与“停机问题”

热度 5 柳渝 2016-7-18 23:20

计算机理论中现在流行的一个最基本术语就是“停机问题”（the Halting Problem），其基本意思是：判断任意一个程序是否会在有限的时间之内结束运行的问题。这种解释一开始就隐含了一个主体上的混乱，“判断者”是谁？ 这个问题实质源于数学和逻辑基本理论，也就是著名的希尔伯特第十问题（Hilbert's tenth problem） ...

个人分类: NP理论|15939 次阅读|10 个评论 热度 5

介绍一个求解SAT问题的程序SatZ（1）

柳渝 2016-7-17 00:30

众所周知SAT问题（SAtisfiability Problem）是逻辑学的一个基本问题，也是算法理论的一个核心问题，众多学者已经为此做出了大量的工作，开发出许多算法程序，称“SAT求解器（SAT solver）”（ https://en.wikipedia.org/wiki/Category:SAT_solvers ），这里介绍其中的一个完备算法的程序－SatZ，供感兴趣的网友运行测试实 ...

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

本页有 1 篇博文因作者的隐私设置或未通过审核而隐藏