代数复杂性中的电路与树：符号转换系统及计算模型解析

### 代数复杂性中的电路与树：符号转换系统及计算模型解析 #### 1. 符号转换系统中的可达性逻辑 在研究符号转换系统的可达性问题时，可达性逻辑 \(L^*_6\) 是一个重要概念。可达性逻辑 \(L^*_6\) 由 \(L^*_5\) - 公式通过特定语法生成，其语法规则为 \(\phi ::= p | \phi \vee \phi | \exists \phi\)，其中 \(p\) 是常量且 \(p \in \Pi\)。 可达性逻辑 \(L^*_6\) 的表达能力比有界可达性逻辑 \(L^*_5\) 弱，这是因为它诱导出的状态等价关系 \(\sim =_6\) 比有界可达等价关系更粗。例如，在图中所有状态 \(s_i\)（\(i \geq 0\)）是可达等价的，但任意两个状态都不是有界可达等价的。 可达等价的定义如下：设 \(S\) 是一个转换系统，\(S\) 的两个状态 \(s\) 和 \(t\) 是可达等价的，记为 \(s \sim =_S^6 t\)，当且仅当对于 \(S\) 的每个以 \(s\) 为源且以 \(p\) 为目标的轨迹，都存在一个以 \(t\) 为源且以 \(p\) 为目标的轨迹，反之亦然。 对于每个具有 \(k\) 个可观察量的符号转换系统 \(R\)，可达等价关系 \(\sim =_R^6\) 最多有 \(2^k\) 个等价类，因此具有有限索引。然而，由于可达性问题对于许多符号转换系统（包括图灵机和多面体混合自动机）是不可判定的，所以不存在用于计算符号转换系统可达等价商的通用算法。 #### 2. 代数复杂性中的计算模型 在代数复杂性中，算法的复杂度通常通过计算过程中执行的基本操作数量来衡量。基本操作一般包括算术运算和比较，有时也允许使用超越函数。即使基本操作集固定，问题的复杂度仍取决于所考虑的具体计算模型，主要的计算模型有电路和树。 ##### 2.1 任意结构 - **结构定义**：“结构” \(M\) 是一个配备了有限个函数 \(f_i : M^{n_i} \to M\) 和关系 \(r_i \subseteq M^{m_i}\) 的集合，其中零元函数称为常量，且结构 \(M\) 包含相等关系。 - **项的定义**： - 变量和 \(M\) 中的元素是深度为 0 的项。 - 深度 \(d \geq 1\) 的项形式为 \(f_i(t_1, \ldots, t_{n_i})\)，其中 \(f_i\) 是 \(M\) 的函数，\(t_1, \ldots, t_{n_i}\) 是最大深度为 \(d - 1\) 的项。包含 \(n\) 个不同变量 \(x_1, \ldots, x_n\) 的项可计算从 \(M^n\) 到 \(M\) 的函数。 - **公式的定义**： - 原子公式形式为 \(r_i(t_1, \ldots, t_{m_i})\)，其中 \(t_1, \ldots, t_{m_i}\) 是项。 - 无量词公式是原子公式的布尔组合，其归纳定义如下： - 原子公式是深度为 0 的公式。 - 若 \(F\) 是深度为 \(d - 1\) 的公式，则 \(\neg F\) 是深度为 \(d\) 的公式。 - 若 \(\max(\text{depth}(F), \text{depth}(G)) = d - 1\)，则 \(F \vee G\) 和 \(F \wedge G\) 是深度为 \(d\) 的公式。包含 \(n\) 个不同变量 \(x_1, \ldots, x_n\) 的公式定义了 \(M^n\) 的一个子集。 - 存在公式形式为 \(\exists x_1 \exists x_2 \cdots \exists x_n F\)，其中 \(F\) 是无量词公式。若每个存在公式都等价于一个无量词公式，则称结构 \(M\) 允许量词消去，这一概念在研究 “\(P_M = NP_M\)?” 问题中起着重要作用。 例如，若 \(M\) 是一个域，\((M, +, \times, =)\) 的项表示多项式，无量词公式定义的集合称为可构造集；若 \(M\) 是一个有序域，\((M, +, \times, \leq)\) 的可定义集是半代数集。 ##### 2.2 树 - **分支树**：具有 \(n\) 个输入变量 \(x_1, \ldots, x_n\) 的分支树以如下方式识别 \(M^n\) 的一个子集。每个内部节点 \(g\) 由 \(M\) 的某个原子公式 \(F_g(x_1, \ldots, x_n)\) 标记，并有两个子节点。若输入满足 \(F_g\)，则向左走；否则向右走。叶子节点标记为接受或拒绝，或者也可以用 \(M\) 的项标记，此时树可计算从 \(M^n\) 到 \(M\) 的函数。分支树的复杂度通过深度衡量，即 \(M^n\