68、可行不完备性：复杂度理论与数学基础的深度关联

可行不完备性：复杂度理论与数学基础的深度关联

在数学领域中，复杂度理论与逻辑之间存在着一些有趣的联系。然而，复杂度理论与逻辑的关联并不意味着它必然与数学基础也存在同样的联系。接下来，我们将深入探讨复杂度理论与数学基础之间更具体的联系，主要围绕一些猜想展开，这些猜想虽带有一定的推测性，但都是具体的数学陈述，原则上可以被证明或反驳。

可行不完备性论题

可行不完备性论题指出，不完备性现象在多项式时间计算层面上有所体现。该论题的提出源于两种不同的思考方向。

一致性问题

由于哥德尔不完备性定理，希尔伯特提出的用有穷主义方法证明数学基础一致性的计划无法实现。当代数学的基础是策梅洛 - 弗兰克尔集合论（Zermelo - Fraenkel Set Theory），要证明其一致性，有穷主义方法远远不够，甚至需要比该理论本身更强的理论。既然无法证明一致性，我们可以考虑是否能证明不存在短的矛盾证明。如果能表明最小的矛盾证明长度非常大，比如至少为 $10^9$，那么在实践中我们就不用担心会遇到这样的证明，这可以看作是希尔伯特计划的部分实现。

给定一个界限 $n$，我们总能找到一个长度至多为指数级的有穷主义证明，来表明给定的一致理论 $T$ 不会通过长度为 $n$ 的证明推出矛盾。这是因为我们可以列出所有长度为 $n$ 的字符串，并逐个证明它们不是矛盾证明。但问题在于，是否存在比这种指数级“暴力”证明更短的证明呢？这就涉及到了指数扩张的问题，也与复杂度理论中的开放问题相关。

证明复杂度

另一个猜想来源是证明复杂度，特别是有界算术理论。主要的开放问题涉及分离与不同复杂度类相关的理论对。我们不仅要证明这些理论可证明的定理