实数机器类的拉德纳结果研究

### 实数机器类的拉德纳结果研究 在计算复杂性理论中，拉德纳定理是一个重要的结论，它揭示了在某些复杂性类之间存在非完全问题。本文将探讨一种受限的实数机器模型下的拉德纳定理，分析该模型的特点以及证明过程中的关键步骤。 #### 受限模型概述 在这个受限的BSS（Blum - Shub - Smale）模型中，对机器常数的使用进行了限制。实数常数可以自由用于加法和减法，但不能相互相乘。这种模型与完整的BSS模型更为接近，并且具有与原模型相同的完全问题，例如求解最多二次的实多项式方程组的可行性问题（FEAS）在该受限模型中是NPrcR - 完全的。 #### 完全问题与对角化 - **FEAS问题的NPrcR - 完全性**：FEAS问题属于NPrcR，因为可以通过编码多项式方程的系数，猜测一个潜在的实解并在该点评估所有多项式来进行验证，且该过程不需要额外的实常数。对于NPrcR - 完全性的证明，通过将NPR - 机器M的计算归约为多项式系统的可行性问题，在构造多项式系统时仅以受限的方式使用机器常数。 - **非完全问题的存在性**：假设FEAS ⊈ PrcR / const（即NPrcR ⊈ PrcR / const），则存在NPrcR \ PrcR / const中的问题在受限多项式时间归约下不是NPrcR - 完全的。 #### 主要结果的证明思路 为了证明PrcR / const = PrcR，从而得出拉德纳定理在该受限模型中成立，主要思路是为每个维度n找到合适的常数选择，使得线性基本机器M能够正确决定L ∩ R≤n。具体步骤如下： 1. **寻找正确方向**：定义En为使得M正确决定L ∩ R≤n的合适常数集合。通过分析En的拓扑结构，利用König无穷引理，证明存在三个向量c∗, d∗, e∗ ∈ Rk，使得对于所有维度n，通过从c∗向d∗方向移动一小步，再向e∗方向移动一小步，最终可以到达En。 2. **高效消除量词**：由于受限机器系数的线性结构，对于形如“∀n ∈ N ∃ϵ1 > 0 ∀μ1 ∈ (0, ϵ1) ∃ϵ2 > 0 ∀μ2 ∈ (0, ϵ2) M(x, c∗ + μ1 · d∗ + μ2 · e∗)正确决定L ∩ R≤n”的断言，可以高效地进行判断。 #### 寻找正确方向的详细过程 - **En的性质**： - 对于所有n ∈ N，En+1 ⊆ En。 - 每个En都是非有限的，因为如果某个En是有限的，则存在一个索引m使得Em = ∅。 - 每个En是有限个凸集的并集，这些凸集是（可能无限的）开或闭半空间的交集。 - En的闭包也具有嵌套