“复杂性理论探索知识极限的 50 年历程”一文，对P versus NP问题的研究进行了精彩的回顾（见下图），特别是追本溯源到希尔伯特计划（其经典表达“判定命题（Entscheidungsproblem）”），使得P versus NP问题与哥德尔，图灵等人的工作联系起来，让文章呈现出同类文章中难见的开阔视野！ 

文章以现在是 IBM 的理论计算机科学家Marco Carmosino的研究生涯为主线：从对哥德尔工作的兴趣转移到对P versus NP问题的研究，面对P versus NP问题研究多年停滞不前的情况，Carmosino说：“这是理论计算机科学中最明显的事实之一，当你遇到一个如此持久的现象时，你需要一些解释。”在突破P versus NP问题困境的努力中，Carmosino与一些学者转向电路复杂性的“最小电路大小问题”（MCSP），将注意力聚焦到P versus NP问题的元复杂性上，取得的一些最新进步。

MCSP问题与在P versus NP问题研究中占据重要地位的SAT问题具有内在的联系：

1. SAT问题（boolean SATisfiability problem）：

给定一个表达为合取范式的布尔公式F，判断F是否可满足，即找出使得公式F为真的布尔变量真值赋值。

例子1：

F= (p∧ q) ∨ (p ∧ r) ∨(q ∧ r)

F是可满足的，有四个解：

p =0, q=1, r=1; 

p =1, q=0, r=1; 

p =1, q=1, r=0; 

p =1, q=1, r=1

F的真值表如下：

2. MCSP问题（Minimum Circuit Size Problem）：

给定一个布尔公式A的真值表，找出最少逻辑操作符数目的表达式。

例子2：

给定一个真值表： 

此真值表可以表达为15个逻辑操作符的布尔公式：

(¬p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ r) ∨(¬p ∧ ¬q ∧ r) ∨(p ∧ q ∧ r)

也可以表达为5个逻辑操作符的布尔公式：

(p∧ q) ∨ (p ∧ r) ∨(q ∧ r)

还可以表达为4个逻辑操作符的布尔公式：

(p∧ q) ∨(r ∧ (p ∨ q)) 

人们在解决SAT问题的途中遇到了所谓的“自然证明障碍”，所以转向电路复杂性的MCSP问题。对此麻省理工学院的复杂性理论家Ryan Williams说：“我的理解是，人们开始研究电路复杂性，是因为他们认为图灵机太复杂了”。

与SAT问题相比，MCSP问题更加注重对问题结构的细致研究，这可能会对NP问题的计算结构有更深入的理解，无疑是一个有意义的研究方向，但SAT问题是P versus NP问题的源头，库克用布尔逻辑公式模拟图灵机得SAT问题，所以因回避图灵机而研究MCSP问题，就可能舍本逐末！

另一方面，人们试图回避图灵机应该是有原因的。我认为，其中一个重要原因是，哥德尔的工作挡在了深入认识图灵机和图灵基于图灵机的可计算性理论的工作（1936年论文）的路上，哥德尔宣称如“说自己是不可证明的”自相矛盾的悖论命题是形式系统中正常的“不可判定命题”，阻碍了人们深入认识图灵关于形式系统中真实的不可判定命题的极富启发性的工作，哥德尔的不完备性定理带给人们启发的同时，更带来难以理清的思想上的纠缠和认知上的困惑，典型的表现就是人们把图灵的工作简化为卡通版的“停机问题”，而“停机问题”的证明正是哥德尔证明的翻版，却不是图灵的工作！

面对解决P verses NP问题的困境，加拿大西蒙Simon Fraser University的复杂性理论家Valentine Kabanets，把对计算极限的推理比作在没有大局意识的情况下勘测广袤的领土，认为一个拥有无限计算能力的人可以从山顶俯瞰全局，但凡人无法指望这种优势：“我们这些在山脚下的人可以试着跳上跳下，以获得更好的视野。”

我认为，并不是一个拥有无限计算能力的“超人”才能从山顶俯瞰全局，而是具有“系统思维”的“凡人”可以获得更好的视野，人们现在意识到P versus NP问题的元复杂性，表明正在走向更广阔的系统思维视野，这也正是我们发起在2024年罗马的世界哲学大会重读哥德尔研讨会的期许：

- 为了促进学术界和公众对哥德尔不完全性定理的反思，我们提议从哲学、逻辑、语言、数学、算法理论和人工智能等不同角度重新审视这个定理，深入到哥德尔1931年论文中定理的原始证明，超越我们思维的局限，共同面对哥德尔证明中隐含的不安。

- 我们相信，对真理的渴望和对真理的追求是化解不安的最根本途径，

新年是一个为生命带来新的愿景的机会和可能性，有清晰愿景的人是幸运的。祝愿我们带着这样清晰的愿景走进2024！

原文：

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

By BEN BRUBAKER，August 17, 2023

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/