n********g
发帖数: 6504 | 1 P和NP表示两种想象中的机器能在多项式时间内能解决问题的类（有条件的集合）。P和
NP是否相等是当今最核心的数学和哲学问题之一。除了计算机，我觉得理工科，乃至文
史哲，了解一下有好处。
首先推荐两本书。21世纪了，不要老看1970年代的书。第一本是科普小册子：《可能与
不可能的边界》。第二本较为专业，但中学程度学生仍然能够读懂：《计算复杂性-现
代方法》。
需要指出的是，大多数数学家相信P是NP的真子集。也许是因为，在哲学上，如果P=NP
，那么“强人工智能”“就一定会实现”，不单只数学家会失业，未来也会是一个不一
样“想像不到”的社会。
我打算简单介绍一下这两种机器、时间复杂性，上世纪经典的推导，及我读到里感觉最
接近证明或证伪的方法。 |
x****o
发帖数: 29677 | |
n********g
发帖数: 6504 | 3 首先，P和NP对应两种不同的机器，分别叫做确定图灵机和不确定图灵机。至于这两种
机器是怎么来的，为什么要长这样，历史学家可以写很多专著。在此就不挖坟了也不重
复维基上已有的内容。关于这两种机器，只需要知道以下几点：
1、确定图灵机每一步都是确定的，每一种情况只有最多一种下一步的可能，也只能严
格按照这种可能走下去。
2、不确定图灵机的下一步可以有多于一种可能，如下棋。奇妙的是每一步都是“正确
”地导向最终结果，或者说可以反悔，“错误”的都不算。
3、两图灵机解题的时候的时间和空间都没有限制。当然时间数总是大于等于空间数。
4、对输入长度为n个符号的问题，P和NP要求时间上界不超过n^k，k是对应具体一个图
灵机一常数。
5、P和NP就是bigcup_{iinmathbb{N}}TIME(n^i)的全集。
首先这两是无穷集合。绝大多数人被吓到了。这可能是为何这个问题的研究走入死胡同
的原因。 |
n********g
发帖数: 6504 | 4 根据历史记载，在俺出生之前，有位叫库克研究自动证明的千老在伯克利没混到天牛，
结果愤然到了北美国图灵呆过的学校多伦多。多年以后，伯克利教廷还得为此道歉。当
然因为是俺出生以前的事，所以真相是否如此，俺也说不准。
另外，在地球另一边也有一位研究电路不得志的年轻人。他两从不同领域出发几乎同时
发现了NP完全。也就是新近被重新命名的库克-李文定理。当然，可惜李文没有南俄罗
斯，所以定理能重新命名，图灵奖没得补发。
这个NP完全俺觉得是为何P vs. NP没被证明的最重要原因。所以花点笔墨说一说。后来
人千万别踩这雷区。
首先，库克没能证明P ? NP。但库克定义了一个测度，发现一个NP的子集（不一定是真
子集）NP完全。NP完全的意思是，假设一个NP完全问题是一个写好的函数，所有NP问题
都能在多项式次（因此总时间仍然是多项式次的）地调用此函数后得到解决。
大致可以这样理解，如果P的测度值定为0，一般NP问题的测度就是正整数，而NP完全库
克希望是无穷（比所有整数都大）。在物理、数学里，无穷通常被认为异常、无解。所
以库克应该是希望以此证明存在NP（完全）问题不在P里。所以如果谁想沟通0和无穷，
证明存在一个P的算法解决一个NP完全问题，真是愚公移山。
还好，库克本人至今也没能证明P不等于NP。
需要进一步指出的是，任何声称找到算法或找到不能解决的NP完全问题的文章，都不会
被学界认真对待。原因见上俺的观点。俺们需要其它门路。 |
n********g
发帖数: 6504 | 5 绕过第一个坑回到原点。比较两个无穷集合，人类唯一的方法就是一一对应，也就是双
手合十，看哪只手有没有多出的手指头。如果没有，就定义为相等，否则就是不相等。
对角线是找到/构造这个不相等（多出手指头）的一个方法。康托尔用它证明实数集比
整数集大。哥德尔用它证明不完备。图灵用它证明判定问题无解。也有人想用它构造NP
中不能被P解决的问题。You know what，还没找到。
到了这里，证明不等的已经黔驴技穷。让我们看看证明相等的怎么样。
由于机器的不同（距离太远/无穷远手不够长），直接双手合十行不通（否则问题也就
不拖到今天了）。和库克的思路类似但作用相反，（可数）无限只手怎么样？也就是说
，我知道我的左手和右手手指是一一对应的。如果有可数无限个这样的人的右手合下一
个人的左手，跨越时空，一直下去到宇宙的尽头把牛郎和织女连起来，能否找到多出的
手指头或都是一一对应的。
数学地说，如果我们定义一个测度，把NP分成子类/集，记为P属于等于NP/0属于等于..
.属于等于NP/i...属于等于NP。如果P等于NP，则无论任何测度（如全男人测或全女人
测），这个式子都必然处处取等号。如果P不等于NP，则这个式子必然存在某一些是真
属于，不等，链断了。
由于测度是我们取的，为了研究方便，不妨其中有一些是相等的，如定义的测度P=NP/0
，乃至P=NP/0=...=NP/i...属于等于NP。所以，问题最后的关键就在于，在这样的尺度
下，最后一个属于等于究竟是真属于还是等于。
附注：定义这样的测度及证明需要深入图灵机的一些基本定理。不难懂学过图灵机的应
该都看得懂但在这里不展开。 |
n********g
发帖数: 6504 | 6 以下来自未经发表/预印的手稿，获授权讨论一下，有需引用可以代为联系。
观察P=NP/0=...=NP/i=...属于等于NP，
(1)如果P=NP，则NP=NP/0 U ... U NP/i U...，也就是NP属于等于NP/0并集NP/1并集..
.。不严格地说，存在NP的测度是无限但不是无穷。
(2)如果P不等于NP，则NP/0并集NP/1并集...是NP的真子集。不严格地说，所有NP的测
度是无穷。
由于无限可能的测度供我们选择。这里要利用图灵机的一个特性：停机。也就是说解决
问题（输入）的机器能工作的时候过程可以是无限但都是有穷的。提示我们也许存在这
么一个无限但有穷的测度，令P=NP。
以上把P vs. NP问题转化为是否存在一个测度的问题。 |
n********g
发帖数: 6504 | 7 我们以前“冒着生命危险”登山的时候，只要队伍里有一个人登顶，就是队伍集体的成
功。
我相信自己对荣耀看得不重。从小上报纸电视足够多了。当你有了100万美元，再来一
个100万金钱上的意义也不那么大。“可以退休”的码工对发文章，当发考题更不会有
很大的兴趣。
我们老帮菜希望看到人类的进步。所以花了一个早上整理了一下关于P和NP的进展和陷
阱。希望对后来的人会有些帮助。
【在 x****o 的大作中提到】
: 你要能证明，图灵奖就是你的
|
s*****V
发帖数: 21731 | 8 这个问题有这么重要么？
NP
【在 n********g 的大作中提到】
: P和NP表示两种想象中的机器能在多项式时间内能解决问题的类（有条件的集合）。P和
: NP是否相等是当今最核心的数学和哲学问题之一。除了计算机，我觉得理工科，乃至文
: 史哲，了解一下有好处。
: 首先推荐两本书。21世纪了，不要老看1970年代的书。第一本是科普小册子：《可能与
: 不可能的边界》。第二本较为专业，但中学程度学生仍然能够读懂：《计算复杂性-现
: 代方法》。
: 需要指出的是，大多数数学家相信P是NP的真子集。也许是因为，在哲学上，如果P=NP
: ，那么“强人工智能”“就一定会实现”，不单只数学家会失业，未来也会是一个不一
: 样“想像不到”的社会。
: 我打算简单介绍一下这两种机器、时间复杂性，上世纪经典的推导，及我读到里感觉最
|
n********g
发帖数: 6504 | 9 我个人觉得没那么重要。否则也就不会一直没人去解。也不会只值100万美元。要知道
谷歌码工改善了其搜索算法一丁点，就捞了百万美元的奖励。说句难听的话，谁搞P vs
. NP都会被认为是不务正业，以至于普遍认为P vs. NP不会由已知的学术界研究人员解
决，只能靠民科。
但换一个角度看，P vs. NP至少和黎曼猜想一样重要。和纳米、量子等时髦概念一样，
无数算法问题被归结为NP完全问题。连学英国比较文学然后研究雷达的白的门都声称自
己发了paper发现又一个NP完全问题。
虽然我有保留，但很多人相信，P=NP意味着他们心目中的世界末日。机器和人工智能会
崛起，再没有隐私，警察国家，等等等等。至少数学家就得大批失业了。因为库克最早
接触这个问题就是因为定理自动证明。
【在 s*****V 的大作中提到】
: 这个问题有这么重要么？
:
: NP
|
n******5
发帖数: 1990 | |
|
|
S******r
发帖数: 4421 | 11 尼玛b sb的一个特征就是一个很清晰的概念 他给你复杂化
P问题的P指的就是多项式 也就是这个问题的复杂度可以用多项式表示。比如给你 x=
100个自然数，傻子也能在10000次比较以内排序好，这个复杂度就是x^2，这就是个多
项式，是P问题
NP指的是nondeterministic polynomial 指的是如果已经告诉你一个问题的答案 你可
以在多项式复杂度内断定答案的正确性
【在 n********g 的大作中提到】
: 首先，P和NP对应两种不同的机器，分别叫做确定图灵机和不确定图灵机。至于这两种
: 机器是怎么来的，为什么要长这样，历史学家可以写很多专著。在此就不挖坟了也不重
: 复维基上已有的内容。关于这两种机器，只需要知道以下几点：
: 1、确定图灵机每一步都是确定的，每一种情况只有最多一种下一步的可能，也只能严
: 格按照这种可能走下去。
: 2、不确定图灵机的下一步可以有多于一种可能，如下棋。奇妙的是每一步都是“正确
: ”地导向最终结果，或者说可以反悔，“错误”的都不算。
: 3、两图灵机解题的时候的时间和空间都没有限制。当然时间数总是大于等于空间数。
: 4、对输入长度为n个符号的问题，P和NP要求时间上界不超过n^k，k是对应具体一个图
: 灵机一常数。
|
n********g
发帖数: 6504 | 12 有人会argue，这只是一个存在性证明的思路，即使证明了P=NP，构造了NP和P之间的一
一对应。对实际运算NP完全问题也没有多大帮助。
其实，这个思路对寻找NP完全的解法也很有帮助。看似别人在大海里捞针，投资自己有
限的生命在无穷的宇宙之前，也要知道自己应该在哪里下网。
注意到，NP完全只是在库克给出的测度上是“无穷”。我们潜在的有无穷无尽可能的测
度。我的感悟是，对付无穷的问题，需要一把无穷的尺子。是否某一个NP完全问题在某
一个特定的测度上测度值不是无穷，如7000万。Eureka！人类从此面临黑暗。
当然，最现实的是找到一个测度，某NP完全问题在此问题上的值是1。而且你能够在书
的空白边上写下如何把这1降为0。
【在 n********g 的大作中提到】
: 我个人觉得没那么重要。否则也就不会一直没人去解。也不会只值100万美元。要知道
: 谷歌码工改善了其搜索算法一丁点，就捞了百万美元的奖励。说句难听的话，谁搞P vs
: . NP都会被认为是不务正业，以至于普遍认为P vs. NP不会由已知的学术界研究人员解
: 决，只能靠民科。
: 但换一个角度看，P vs. NP至少和黎曼猜想一样重要。和纳米、量子等时髦概念一样，
: 无数算法问题被归结为NP完全问题。连学英国比较文学然后研究雷达的白的门都声称自
: 己发了paper发现又一个NP完全问题。
: 虽然我有保留，但很多人相信，P=NP意味着他们心目中的世界末日。机器和人工智能会
: 崛起，再没有隐私，警察国家，等等等等。至少数学家就得大批失业了。因为库克最早
: 接触这个问题就是因为定理自动证明。
|
n********g
发帖数: 6504 | 13 这是库克在P vs. NP问题官方描述中给出的另一个毁人无数的陷阱。对解决P vs. NP问
题毫无帮助。所以我避免提及这个。
但是，这个能帮助理解NP的哲学意义，及NP为何重要。
【在 S******r 的大作中提到】
: 尼玛b sb的一个特征就是一个很清晰的概念 他给你复杂化
: P问题的P指的就是多项式 也就是这个问题的复杂度可以用多项式表示。比如给你 x=
: 100个自然数，傻子也能在10000次比较以内排序好，这个复杂度就是x^2，这就是个多
: 项式，是P问题
: NP指的是nondeterministic polynomial 指的是如果已经告诉你一个问题的答案 你可
: 以在多项式复杂度内断定答案的正确性
|
l**a
发帖数: 11 | 14 真心赞
【在 n********g 的大作中提到】
: 这是库克在P vs. NP问题官方描述中给出的另一个毁人无数的陷阱。对解决P vs. NP问
: 题毫无帮助。所以我避免提及这个。
: 但是，这个能帮助理解NP的哲学意义，及NP为何重要。
|
h**c
发帖数: 1979 | |
n********g
发帖数: 6504 | 16 和库克定义的测度不同。库克试图定义一个测度，使NP完全问题的测度为无穷。因此（
潜意识地）证明NP完全问题不属于P。
如果要证明P=NP，按照我上面提到的要求：
1、这个测度的可能值不包括无穷。满足这个的很多，如图灵机使用的时间、空间等可
以无限但都有穷；
2、P=NP/0；
3、可以证明NP/i+1属于等于NP/i。所以P=NP/0=...=NP/i=...
几年前一篇预印给出了这样一个测度：图灵机解决问题的所有步骤中需要"猜/不确定"
多少次。
1、很显然，图灵机不会猜无穷次。否则就是永不停机；
2、很显然，P=NP/0。因为猜0次的不确定图灵机就是确定图灵机。双手合十一一对应。
3、不失一般性，假设NP/i里所有图灵机都是单带。通过两个巧妙的转换：(1)将属于NP
/i+1的单带图灵机用一个多带图灵机模拟其第i+1次猜测的每一种可能。这个多带图灵
机时间复杂度一样但只猜了i次；(2)用一单带图灵机模拟此多带图灵机，通过增加时间
复杂性(t^2)换取回到单带。这样，用增加时间复杂性换取"猜/不确定"测度下降。注意
：对多项式时间函数t而言，t^2也是多项式时间。这就证明了NP/i+1属于等于NP/i。
【在 h**c 的大作中提到】
: 这个测度是咋定义出来的？
|
T*******x
发帖数: 8565 | 17 你这个符号NP/i，你定义了吗？我没看懂。
NP
【在 n********g 的大作中提到】
: 绕过第一个坑回到原点。比较两个无穷集合，人类唯一的方法就是一一对应，也就是双
: 手合十，看哪只手有没有多出的手指头。如果没有，就定义为相等，否则就是不相等。
: 对角线是找到/构造这个不相等（多出手指头）的一个方法。康托尔用它证明实数集比
: 整数集大。哥德尔用它证明不完备。图灵用它证明判定问题无解。也有人想用它构造NP
: 中不能被P解决的问题。You know what，还没找到。
: 到了这里，证明不等的已经黔驴技穷。让我们看看证明相等的怎么样。
: 由于机器的不同（距离太远/无穷远手不够长），直接双手合十行不通（否则问题也就
: 不拖到今天了）。和库克的思路类似但作用相反，（可数）无限只手怎么样？也就是说
: ，我知道我的左手和右手手指是一一对应的。如果有可数无限个这样的人的右手合下一
: 个人的左手，跨越时空，一直下去到宇宙的尽头把牛郎和织女连起来，能否找到多出的
|
n********g
发帖数: 6504 | 18 P和NP是两个语言的类。是所有图灵机能接收(accept)语言的子类（满足图灵机类型及
时间限制）。
语言就是一个图灵机能接收的输入符号串的集合（所以所有符号串都是停机的）。通常
一个图灵机m能接受的语言记为L(m)。
定义一个语言的函数（测度），f(L(m))，NP/i这个记号在这里定义为属于NP的的子集{
L(m) in NP : f(L(m))<=i}。
【在 T*******x 的大作中提到】
: 你这个符号NP/i，你定义了吗？我没看懂。
:
: NP
|
n********g
发帖数: 6504 | 19 在这里给一个小彩蛋。乍一看，所有NP完全问题都猜得上不封顶，但这个有限猜的次数
其实很有现实意义。
如排序就是一个NP难问题，可以转化为不确定地猜一次然后验证解决。因此可以在不超
过O(n^2)时间内确定地解决。
在数学和计算机科学里，排序/有序是基础地重要。NP重要，虽然数学家可能没有意识
到，他们遇到解决过无数NP难的问题。这些方法构成了数学的基础。
【在 n********g 的大作中提到】
: P和NP是两个语言的类。是所有图灵机能接收(accept)语言的子类（满足图灵机类型及
: 时间限制）。
: 语言就是一个图灵机能接收的输入符号串的集合（所以所有符号串都是停机的）。通常
: 一个图灵机m能接受的语言记为L(m)。
: 定义一个语言的函数（测度），f(L(m))，NP/i这个记号在这里定义为属于NP的的子集{
: L(m) in NP : f(L(m))<=i}。
|
s***h
发帖数: 487 | 20 排序是 NP Hard？
: 在这里给一个小彩蛋。乍一看，所有NP完全问题都猜得上不封顶，但这个有限猜
的次数
: 其实很有现实意义。
: 如排序就是一个NP难问题，可以转化为不确定地猜一次然后验证解决。因此可以
在不超
: 过O(n^2)时间内确定地解决。
: 在数学和计算机科学里，排序/有序是基础地重要。NP重要，虽然数学家可能没
有意识
: 到，他们遇到解决过无数NP难的问题。这些方法构成了数学的基础。
【在 n********g 的大作中提到】
: 在这里给一个小彩蛋。乍一看，所有NP完全问题都猜得上不封顶，但这个有限猜的次数
: 其实很有现实意义。
: 如排序就是一个NP难问题，可以转化为不确定地猜一次然后验证解决。因此可以在不超
: 过O(n^2)时间内确定地解决。
: 在数学和计算机科学里，排序/有序是基础地重要。NP重要，虽然数学家可能没有意识
: 到，他们遇到解决过无数NP难的问题。这些方法构成了数学的基础。
|
|
|
S******r
发帖数: 4421 | 21 Stop shitting
Sorting is a P problem, which certainly makes it an NP problem.
But it is not an NP-hard problem
【在 n********g 的大作中提到】
: 在这里给一个小彩蛋。乍一看，所有NP完全问题都猜得上不封顶，但这个有限猜的次数
: 其实很有现实意义。
: 如排序就是一个NP难问题，可以转化为不确定地猜一次然后验证解决。因此可以在不超
: 过O(n^2)时间内确定地解决。
: 在数学和计算机科学里，排序/有序是基础地重要。NP重要，虽然数学家可能没有意识
: 到，他们遇到解决过无数NP难的问题。这些方法构成了数学的基础。
|
n********g
发帖数: 6504 | 22 这个是我在中文英文之间转换出问题了。
我想说的是排序可以在不确定图灵机里以O(n)时间解决。
【在 S******r 的大作中提到】
: Stop shitting
: Sorting is a P problem, which certainly makes it an NP problem.
: But it is not an NP-hard problem
|
T*******x
发帖数: 8565 | 23 图灵机我不太懂。p=np问题我看了wiki的介绍，和你以图灵机方式的介绍有一个转换问
题。p和np谈论的是“problem”的集合，而你这里谈论的是图灵机能接受的语言的集合
。一个problem和一个语言是什么关系？能不能介绍一下？
集{
【在 n********g 的大作中提到】
: P和NP是两个语言的类。是所有图灵机能接收(accept)语言的子类（满足图灵机类型及
: 时间限制）。
: 语言就是一个图灵机能接收的输入符号串的集合（所以所有符号串都是停机的）。通常
: 一个图灵机m能接受的语言记为L(m)。
: 定义一个语言的函数（测度），f(L(m))，NP/i这个记号在这里定义为属于NP的的子集{
: L(m) in NP : f(L(m))<=i}。
|
b****d
发帖数: 1311 | 24 楼主似乎是想用cardinality的比较 |P|<|NP| 的思路证明P不等于NP。 |
d*c
发帖数: 1 | |
P******o
发帖数: 505 | 26 zan ..............
【在 S******r 的大作中提到】
: 尼玛b sb的一个特征就是一个很清晰的概念 他给你复杂化
: P问题的P指的就是多项式 也就是这个问题的复杂度可以用多项式表示。比如给你 x=
: 100个自然数，傻子也能在10000次比较以内排序好，这个复杂度就是x^2，这就是个多
: 项式，是P问题
: NP指的是nondeterministic polynomial 指的是如果已经告诉你一个问题的答案 你可
: 以在多项式复杂度内断定答案的正确性
|
n********g
发帖数: 6504 | 27 Problem这个是很“民科”的术语。标准的术语是图灵机，图灵机接收的语言以及语言
的集合和类（有限制条件的集合）。
作为翻译对应，首先你有一个机器，可以是齿轮可以电子可以是图灵机，这个叫计算模
型。
然后你有一个问题让机器计算，这个叫输入。
然后机器要么停机要么不停机。如果停机你就有了结果。结果有很多种，但不失一般性
，yes/no就够了。按照yes/no可以将输入分为两个集合。这个输入的集合被称为语言。
一个图灵机可以解决一类问题，这些问题problem的集合被称为语言。
不同图灵机能接受的语言构成P、NP这些类。
如P就是所有确定图灵机（计算模型）在问题输入串长度多项式时间函数内能接受语言
的集合。
【在 T*******x 的大作中提到】
: 图灵机我不太懂。p=np问题我看了wiki的介绍，和你以图灵机方式的介绍有一个转换问
: 题。p和np谈论的是“problem”的集合，而你这里谈论的是图灵机能接受的语言的集合
: 。一个problem和一个语言是什么关系？能不能介绍一下？
:
: 集{
|
n********g
发帖数: 6504 | 28 这其实是库克的想法。我上面提到的本质上只是将问题转换，但倾向于证明P=NP。
难得有人有兴趣，经过周末的聊骚，除了上面没有什么争议的内容，还是有点新料爆。
以下为未经发表/预印的内容：
现在的争议点在于，所有NP/i的并集是否构成NP这个集合的上界。
如果是上界，则夹逼定理，上界是P，下界也是P，则P=NP。
这个上界很不直观。我研究极限的gut告诉我这没问题。但99%的数学博士、计算机科学
博士怕认为是胡说八道。不严格证明或证明有漏洞paper直接枪毙。
想象一下，这就类似于一个极限。极限究竟是实体还是一个永不停机的过程，数学家、
博士们都还在相互拍砖打架。
现在有两种教科书式的证明，第一种是用区间套；第二种是戴尔金分割。都不直观。要
完善补充这一部分征询更多意见后再投稿。预计在年底或明年年初。
【在 b****d 的大作中提到】
: 楼主似乎是想用cardinality的比较 |P|<|NP| 的思路证明P不等于NP。
|
T*******x
发帖数: 8565 | 29 嗯。有一定解释。谢谢。
这样，我换一个角度再问一个问题。就说p吧，p是一个集合，是什么的集合？是问题的
集合？是语言的集合？是输入的集合？什么是集合的一个元素？
【在 n********g 的大作中提到】
: Problem这个是很“民科”的术语。标准的术语是图灵机，图灵机接收的语言以及语言
: 的集合和类（有限制条件的集合）。
: 作为翻译对应，首先你有一个机器，可以是齿轮可以电子可以是图灵机，这个叫计算模
: 型。
: 然后你有一个问题让机器计算，这个叫输入。
: 然后机器要么停机要么不停机。如果停机你就有了结果。结果有很多种，但不失一般性
: ，yes/no就够了。按照yes/no可以将输入分为两个集合。这个输入的集合被称为语言。
: 一个图灵机可以解决一类问题，这些问题problem的集合被称为语言。
: 不同图灵机能接受的语言构成P、NP这些类。
: 如P就是所有确定图灵机（计算模型）在问题输入串长度多项式时间函数内能接受语言
|
n********g
发帖数: 6504 | 30 其实是两个层次，问题的集合的集合。
某图灵机接收的语言={问题或输入 | 被某图灵机接收}
（语言）类={语言 | 类定义}
P、NP都是语言类。
举例说，有一台图灵机会排序，则所有可能的输入串（问题）构成这台图灵机所能接收
的语言。另一个图灵机会找到输入串中最大/最小/平均数。这些图灵机接收的语言是P
的子集，都属于P这个类。当然也属于NP。P是特殊的NP。
【在 T*******x 的大作中提到】
: 嗯。有一定解释。谢谢。
: 这样，我换一个角度再问一个问题。就说p吧，p是一个集合，是什么的集合？是问题的
: 集合？是语言的集合？是输入的集合？什么是集合的一个元素？
|
|
|
n********g
发帖数: 6504 | 31 这些问题、输入、语言的定义在计算复杂性中不重要。
因为计算复杂性不讨论为什么图灵机重要有用，或P=NP如何改变世界。
只就事论事讨论某种图灵机处理问题需要的资源（复杂性）。
P
【在 n********g 的大作中提到】
: 其实是两个层次，问题的集合的集合。
: 某图灵机接收的语言={问题或输入 | 被某图灵机接收}
: （语言）类={语言 | 类定义}
: P、NP都是语言类。
: 举例说，有一台图灵机会排序，则所有可能的输入串（问题）构成这台图灵机所能接收
: 的语言。另一个图灵机会找到输入串中最大/最小/平均数。这些图灵机接收的语言是P
: 的子集，都属于P这个类。当然也属于NP。P是特殊的NP。
|
n********g
发帖数: 6504 | 32 嗯，对没学过图灵机的我觉得需要补充几点。
1、语言、类这些概念如果我没记错就是一般集合论里的概念。没有特别的如计算机语
言之类的含义。
2、相同的语言可以被无数不同的图灵机接收。类似于无数不同的程序都排序。所以比
较语言集，没人比较图灵机集。
P=NP的意思就是每一个被不确定图灵机多项式时间接收的语言（输入集合）都存在确定
图灵机多项式时间接收。
一个比喻就是，如果有一个算法能（不确定地）猜到排序后的结果然后只需验证一下，
存在一个算法（确定地）老老实实一步一步地排序也能算出来。
P和NP涉及两种机器，两个世界。一个凡尘，另一个是魔法世界。
【在 n********g 的大作中提到】
: 这些问题、输入、语言的定义在计算复杂性中不重要。
: 因为计算复杂性不讨论为什么图灵机重要有用，或P=NP如何改变世界。
: 只就事论事讨论某种图灵机处理问题需要的资源（复杂性）。
:
: P
|
w**********g
发帖数: 5486 | |
T*******x
发帖数: 8565 | 34 嗯。基本上懂了。谢谢。
P
【在 n********g 的大作中提到】
: 其实是两个层次，问题的集合的集合。
: 某图灵机接收的语言={问题或输入 | 被某图灵机接收}
: （语言）类={语言 | 类定义}
: P、NP都是语言类。
: 举例说，有一台图灵机会排序，则所有可能的输入串（问题）构成这台图灵机所能接收
: 的语言。另一个图灵机会找到输入串中最大/最小/平均数。这些图灵机接收的语言是P
: 的子集，都属于P这个类。当然也属于NP。P是特殊的NP。
|
m**********e
发帖数: 12525 | 35 妈的,
计算复杂性(现代方法)一书,祖国有卖英文版,也有卖中文翻译版的
你竟然买了本中文翻译版的书
难道阴文这么差?
NP
【在 n********g 的大作中提到】
: P和NP表示两种想象中的机器能在多项式时间内能解决问题的类（有条件的集合）。P和
: NP是否相等是当今最核心的数学和哲学问题之一。除了计算机，我觉得理工科，乃至文
: 史哲，了解一下有好处。
: 首先推荐两本书。21世纪了，不要老看1970年代的书。第一本是科普小册子：《可能与
: 不可能的边界》。第二本较为专业，但中学程度学生仍然能够读懂：《计算复杂性-现
: 代方法》。
: 需要指出的是，大多数数学家相信P是NP的真子集。也许是因为，在哲学上，如果P=NP
: ，那么“强人工智能”“就一定会实现”，不单只数学家会失业，未来也会是一个不一
: 样“想像不到”的社会。
: 我打算简单介绍一下这两种机器、时间复杂性，上世纪经典的推导，及我读到里感觉最
|
n********g
发帖数: 6504 | 36 无论何种语言其实都在说同样的事。有不同作者不同语言写的可以相互对照有利于理解。
人在美国读的英文太多了。读一读中文版可以确认一下。
那本《现代方法》是我见到写得最好的。没那么晦涩。当然，历史部分还可以丰富一下。
【在 m**********e 的大作中提到】
: 妈的,
: 计算复杂性(现代方法)一书,祖国有卖英文版,也有卖中文翻译版的
: 你竟然买了本中文翻译版的书
: 难道阴文这么差?
:
: NP
|
