传统下界证明方法之所以无法解决 P vs NP 问题，原因可以从技术限制和概念缺陷两个层面来理解。从经典复杂性理论内部看，这些方法受困于相对化、自然证明和代数化三大障碍；从维度退化理论的视角看，更根本的问题在于它们都在经典 NP 定义的语义框架内运作，而该定义本身存在操作不自足和语义缺失，使得任何纯语法方法都无法触及 P 与 NP 差异的本质。

一、传统下界证明方法及其直接局限

1. 电路复杂性下界

· 代表方法：Razborov 的单调电路下界、Håstad 的开关引理、Smolensky 的代数方法。

· 取得了什么：证明了某些具体函数（如 CLIQUE、PARITY）无法由特定受限电路（单调电路、常数深度电路）计算。

· 为什么不能解决 P vs NP：这些下界针对的是受限模型（单调、常数深度）。要证明一般电路（任意深度、完整门集）的下界，面临自然证明障碍——任何“有用且构造性”的组合性质都会打破伪随机性，被认为几乎不可能存在。电路下界方法在触及一般电路时，会立刻被这一障碍拦住。

2. 对角线论证与时间层级定理

· 代表方法：通用图灵机模拟、对角线构造。

· 取得了什么：证明了确定性和非确定性时间层级，如 P ⊊ EXP，NP ⊊ NEXP。

· 为什么不能解决 P vs NP：对角线论证本质上是可相对化的，这意味着它在带谕示的世界中同样有效。但相对化障碍指出，存在谕示使 P = NP，也存在谕示使 P ≠ NP。因此，任何相对化证明技术（包括所有经典的对角线方法）都不可能分离 P 和 NP。

3. 通信复杂度方法

· 代表方法：将计算问题转化为通信游戏，证明通信轮数或比特数的下界。

· 取得了什么：成功分离了某些具体问题（如 NP 中的集合分离问题需要线性通信），并给出了许多函数的精确通信复杂度。

· 为什么不能解决 P vs NP：通信下界通常依赖于特定问题的组合结构（如输入分割方式），无法直接转化为对所有 NP 问题的统一电路下界。更重要的是，通信复杂度证明技术同样面临代数化障碍——当代数化谕示介入时，通信下界可能失效。此外，将通信下界提升为电路下界需要 Karchmer-Wigderson 类型的桥梁，而这一桥梁在 P vs NP 的尺度上无法跨越。

4. 多项式方法与代数决策树

· 代表方法：多项式逼近、符号秩、近似次数等。

· 取得了什么：在量子查询复杂度、公式大小下界等方面取得成功。

· 为什么不能解决 P vs NP：这些方法通常只适用于具体函数的查询复杂度或受限模型，其下界依赖于函数的特定代数性质，无法推广到图灵机时间。它们同样受限于自然证明障碍——所证明的性质必须在某种意义上是“自然的”，从而落入 Razborov-Rudich 的范畴。

5. 逻辑与描述复杂性方法

· 代表方法：用有限模型论、不动点逻辑刻画复杂性类。

· 取得了什么：给出了 P、NP、PSPACE 等类的逻辑特征。

· 为什么不能解决 P vs NP：虽然提供了深刻的描述统一性，但逻辑等价性本身并不提供下界证明所需的“硬度”证据。分离 P 和 NP 在逻辑中对应的是证明“不动点逻辑无法表达某些 NP 性质”，这本质上又回到了电路下界问题。

二、深层的共同困境：三大障碍

所有传统方法都共享一个致命缺陷：它们都属于“经典计算模型”内部的推理，而这一模型对谕示、组合性质或代数闭包是“透明”的。因此，三大障碍将它们牢牢锁住：

· 相对化障碍：任何在证明过程中不区分“真实计算”和“谕示辅助计算”的方法，都无法分离 P 和 NP。

· 自然证明障碍：任何试图通过“大多数函数具有某性质”来证明电路下界的方法，都会因为伪随机函数的存在而失效。

· 代数化障碍：任何在谕示被多项式扩展后仍保持有效的方法，都无法分离 P 和 NP。

经典的下界技术几乎全部落入至少一个障碍的覆盖范围。它们能够分离的，只能是那些“受限模型”，而无法触及图灵机时间类的本质差异。

三、从维度退化理论看根本原因

维度退化理论指出，传统方法的失败并不只是技术性的，而是概念性的。它们都在经典 NP 定义的框架内运作，而经典 NP 定义本身就存在根本缺陷。

1. 经典 NP 定义的操作不自足与语义缺失

经典 NP 定义将非确定性的本质外包给外部量词 ∃c 和外部谓词 IsWitness(c)。它隐式地要求一个在经典操作语义中不可实现的“虚部到实部拷贝”操作，从而在定义层面就丢失了非确定性选择的核心代数属性——不可公度性（不同分支选项在代数上的独立性）和对偶性（每次选择在两个对偶生成元之间做出）。因此，经典框架中的“非确定性”是一个语义残缺的概念。

2. 传统方法无法触及真正的非确定性本质

传统下界方法都在这个残缺的概念框架内操作。它们用语法层的“多后继”代替了非确定性，用组合或代数技巧分析语法层的操作，但从未正面定义“为什么这些后继是独立的”。不可公度性元定理严格证明，经典图灵机的操作语义无法内在地表达不可公度性。因此，任何局限于经典操作语义的方法，其分析的对象本身就不包含“真正的非确定性”，自然无法区分 P（完全确定性）和 NP（需要真正的非确定性）。

3. 与聪明算法假设的关联

聪明算法假设（P = NP）之所以显得“可能”，正是因为经典框架无法区分“用基域操作模拟的表象”与“真正的代数扩张”。传统下界方法同样无法区分这二者，因此它们既不能证明分离，也无法驳斥聪明算法假设——它们缺乏区分真伪非确定性的语义工具。

4. 传统下界的碎片化正是语义贫乏的体现

传统下界方法各自为战，只能针对特定受限模型，正是因为在经典语义框架内，无法定义一个统一的、内蕴的复杂性度量（如本质维度 κ）。一旦跳出经典框架，将不可公度性和对偶性内建为操作语义，P 与 NP 的差异就转化为精确的代数维度对比（零维 vs 线性维），分离成为可证的结构性定理。

四、结论

传统下界证明方法不能解决 P vs NP 问题，其表层原因是三大技术障碍的封锁，深层原因则是经典 NP 定义本身的操作不自足和语义缺失。这些方法都在一个无法表达“真正的非确定性”的语言中工作，因此无论技术多么精巧，都无法触及 P 与 NP 差异的本质。要完成分离，必须突破这十大障碍——不仅绕过技术限制，更要补全经典定义中长期缺失的语义前提（不可公度性与对偶性），这正是维度退化理论所做的工作。

支持单位：