可能与不可能的边界的笔记(3)

按有用程度 按页码先后 最新笔记

• 

  展开 收起

  第8页 1.5 漫漫长途

  MagicLee

  库尔特·哥德尔证明数学不能解决所有的问题 在 数理逻辑 中，哥德尔不完备定理是 库尔特·哥德尔 于1931年证明并发表的两条 定理 。简单地说，第一条定理指出：“任何 相容 的 形式系统 ，只要蕴涵 皮亚诺算术公理 ，就可以在其中构造在体系中不能被 证明 的真命题，因此通过推演不能得到所有真命题（即体系是不完备的）。” 把第一条定理的证明过程在体系内部形式化后，哥德尔证明了他的第二条定理。该定理指出：“任何 相容 ...

  2017-02-18 15:27:45

• 

  展开 收起

  第1页 第1章

  秋风

  P/NP问题，从概念上理解，NP是存在解的问题集合，P是能很快找到解的问题集合。P=NP意味着计算机总能很快地计算出任何问题的解。 对NP问题可以很快验证其一个解的有效性，但是不能找到给出快速解的算法，团、Hamilton回路、地图填色和最大割都是NP中的典型例子。对P类问题可以很快找到最优解，如最短路径、配对、欧拉回路和最小割。 斯蒂芬·库克证明NP中的每一个问题都可以通过某种方式归约到可满足性问题，解决了可满足性问题...

  2016-03-02 16:50:40

• 

  展开 收起

  第98页 6.2 启发式方法

  文斗士 (实事求是)

  17世纪的伐木工在测量中经常用他们拇指的长度来大致度量1“英寸”的距离。“拇指规则”这一俗语可能就源自于此，意思是在决定某些问题答案的过程中使用一种不太准确但大致可用的简化方法。言语“朝霞不出门，晚霞行千里”给出了一种粗略但通常相当可靠的预测天气的方式。摩尔定律本身也提供了一种粗略的预测未来计算机的计算能力的方法。 一直没搞清拇指规则是啥，原来写书的西方人都搞不清，哈哈，不过作者的这个推测看着还是...

  2015-01-17 01:06:51