转发老科普：Complexity Theory’s 50-Year Journey

[forecasting]

Complexity Theory’s 50-Year Journey to the Limits of Knowledge

里面牵涉自我指涉，自然证明，元计算复杂度等等，还是写得很有意思。

https://www.quantamagazine.org/complexi ... -20230817/

[牛河梁]

看了一下。请原谅老牛老了，谷歌翻译成中文地看。

1/ 本文最大的问题，也是P vs NP “研究者”们的问题，是这一句话：“如果是这样，那么 P = NP：这两个类是等价的。如果是这样，就一定存在某种算法，能够让解决海量数独难题、优化全球航运路线、破解最先进的加密技术以及自动化数学定理证明变得轻而易举。”这是一个没有根据的愿想。为什么不可能是P = NP，但不存在一个one size fit all的算法能用P解决NP问题。

2/ 老牛（当年）认为，P vs NP之所以“难”，99%的原因是库克把路给带偏了。本文也是如此。在描述NP时，库克使用了另类定义，猜测—验证。而不是原始定义，不确定图灵机。两者等价可以互相推导。但老牛相信使用已经充分确立的不确定图灵机，而不是各种各样的新兴模型，去证明证伪会容易（理解验证）很多。

3/ 老牛认为，P vs NP就像，物理千老居多计算机科班笑而不语的，量子运算一样已经跑偏了。研究者们多是研究其它算法的，然后希望如果P = NP或者P不等于NP就好了，对此发一篇文章。对真正解决P vs NP毫无帮助。

P vs NP问题在买提（以前）无人关注。暑假老牛腾空了1-2个月。有点时间。也许可以思考，联系一下老朋友们，一下。不过雅利安甲骨文就要放一放了。

1/ 老牛仍然认为，像图灵等一样，构造介乎于P和NP之间一个能力不减的可数无穷序列。下接P，上（希望）接NP。如果P = NP，那么这个数列就会collapse成全部项相等。可能是解决问题的核心。注意，库克其实也这么干。只不过他希望构造序列，前面所有非负整数项都相等，最后一个（下标\omega）NPC不等，从而证明P不等于NP。但库克显然这么多年了都无法证明证伪最后一步。

2/ 老牛认为，能否构造一个没有\omega的，或者说\omega项为空集的是证明P = NP的关键。不过反之不一定P不等于NP，参考1/。

3/ 老牛认为，图灵机有一个特点，其接收语言里的每一个输入，都不能使用无限（\omega）那么多的资源。否则就永不停机了。违反了图灵机接受输入的定义。所以，这个候选无穷序列和资源相关。

4/ 老牛认为，P确定图灵机和NP不确定图灵机的区别在于NP有不确定的move。而这个不确定move也是一个可计量的资源（不多于time）。因此可以构造一个使用多少不确定move作为序列。P就是0不确定move的NP(0)。然后是NP(1)、NP(2)等等等等。直至NP。

5/ NP(i)和NP(i+1)之间很容易模拟对应，因此很容易证明P=NP(i) for all i。

6/ 最后一步还要再想一下如何表述才容易被公众接受。举例说这个序列的NP(\omega) = Empty。

Complexity Theory’s 50-Year Journey to the Limits of Knowledge

里面牵涉自我指涉，自然证明，元计算复杂度等等，还是写得很有意思。

https://www.quantamagazine.org/complexi ... -20230817/

[AnonymityFreedom]

Complexity Theory’s 50-Year Journey to the Limits of Knowledge

里面牵涉自我指涉，自然证明，元计算复杂度等等，还是写得很有意思。

https://www.quantamagazine.org/complexi ... -20230817/

这个故事讲得比较完整， 不枯燥， 但是有些用词不准确。

这玩意太理论了。 不少结果没有太大的实际意义。 比如， 即使证明了Pessiland 或者Heuristica不存在，又有什么实际意义呢？

如果能证明Algoritmica存在, 或者Minicrypt/Cryptomania不存在， 那个会是很颠覆性的。 但是可能性不大

[TheMatrix]

看了一下。请原谅老牛老了，谷歌翻译成中文地看。

1/ 本文最大的问题，也是P vs NP “研究者”们的问题，是这一句话：“如果是这样，那么 P = NP：这两个类是等价的。如果是这样，就一定存在某种算法，能够让解决海量数独难题、优化全球航运路线、破解最先进的加密技术以及自动化数学定理证明变得轻而易举。”这是一个没有根据的愿想。为什么不可能是P = NP，但不存在一个one size fit all的算法能用P解决NP问题。

我也倾向于这么认为。

[heteroclinic]

我来跟一下浅见
实践与纯理论的路径选择
比如路径问题,流体和动力的肯定先做实验吹一吹,加加压用染色剂标识一下.EE也有路径问题,比如super node,super mesh,我忘了或者说没有尝试过用相同的手段能否解决图论里简单图的规划.
理论家对公司里的工程问题政治问题毫无概念
比如工程设计文档,可行性评估,验收手段.培养出来的CS, SE 学生被呼叫满产的con artist 打的希腊哗啦. 同时人工只能打筛子,量子力学几近玄学.这两三年AI算是整和了很多模式识别自然语言处理很多好玩的东西到应用,这个不能否认.
我觉得一些没有被谈到的问题,文章扫了五分钟
比如复杂系统除零的问题--高异常反馈,高不稳定输出
用现代动态系统应用数学理论分析混乱行为等


最后一个是瞎说,能否用弗里页变换解决图论问题等,组织行为学里的3G NP 问题,人工职能 con artist filter 等等

[heteroclinic]

组织行为学里的3G NP 问题
记得当年某FAANG的3G写了个NP的问题的文章,被拿到海牛上吹捧
it is f**king joke.