分层项演绎问题的NP完全性结果

### 分层项演绎问题的NP完全性结果 #### 1. 演绎问题概述 将归结和调解提升到分层子句并非易事，需要复杂的算法。其中一个明显的要求是分层项的合一，但对于调解或包含关系等操作，还需要完成一些不太简单的任务，这些任务本身看起来就相当复杂。例如，判断元素是否属于集合 $S[T]$ 时，采用的是指数时间算法。 下面是直接在分层项上表达的决策问题，分层项可以用字符串来指定。由于字符串和出现位置之间的转换在时间和空间上都是线性的，所以可以忽略 $t$ 和 $string(t)$ 之间的区别。合一的定义是将某些常量符号（$V$ 中的那些）视为变量。 | 编号 | 问题 | 实例 | 问题描述 | | ---- | ---- | ---- | ---- | | 1 | 分层成员关系 | $t, T$ | $t \in S[T]$ | | 2 | 分层子项 | $t, T$ | $\exists t' \in S[T] / t$ 是 $t'$ 的子项 | | 3 | 分层交集 | $T_1, T_2$ | $S[T_1] \cap S[T_2] \neq \emptyset$ | | 4 | 分层可合一性 | $T_1, T_2, V$ | $\exists t_1 \in S[T_1], \exists t_2 \in S[T_2] / t_1$ 和 $t_2$ 是可合一的 | | 5 | 分层包含关系 | $T_1, T_2$ | $S[T_1] \subseteq S[T_2]$ | 这些问题之间存在一些简单的关系。通过多项式变换进行归约的关系用 $\propto$ 表示。 **引理 5**： - (i) 分层成员关系 $\propto$ 分层包含关系，且分层成员关系 $\propto$ 分层交集； - (ii) 分层成员关系 $\propto$ 分层子项； - (iii) 分层交集 $\propto$ 分层可合一性。 **证明**： - (i) 将 $t$ 视为分层项，则 $S[t] = \{t\}$，所以 $t \in S[T] \Leftrightarrow S[t] \subseteq S[T] \Leftrightarrow S[t] \cap S[T] \neq \emptyset$。 - (ii) 如果 $t$ 和 $T$ 的出现次数相同，令 $t' = t$；否则，令 $t'$ 为某个新的常量符号。从 $t, T$ 到 $t', T$ 的变换是多项式的，并且 $t \in S[T]$ 当且仅当 $t'$ 是 $S[T]$ 中某个成员的子项。 - (iii) 一致地将 $T_1, T_2$ 中的所有变量替换为新的常量符号，得到 $T_1', T_2'$，它们可合一当且仅当 $S[T_1]$ 和 $S[T_2]$ 有一个公共元素。 接下来证明前四个问题属于 NP。为此，需要为这些问题找到多项式见证。这里考虑群成员关系问题，该问题定义在 $\{1, \ldots, n\}$ 的排列序列 $\sigma, \sigma_1, \ldots, \sigma_m$ 上，询问 $\sigma$ 是否是由 $\sigma_1, \ldots, \sigma_m$ 生成的群的成员。 **引理 6**：问题 1 到 4 都属于 $NP^{Group Membership}$。 **证明**：以分层成员关系问题为例进行证明，对于其他三个问题，由于标准项的可合一性测试是多项式的，所以可以得到相同的结果。根据定理 3 可知 $S[T] = string(um(T G(T)))$，所以 $t \in S[T]$ 当且仅当 $\exists \pi \in G(T)$ 使得 $t = string(um(T \pi))$。 给定 $t$ 和 $T$，首先将 $T$ 表示在出现位置集合 $O = \{1, \ldots, n\}$ 上，只需猜测一个 $\pi \in Sym(O)$ 并首先检查 $t = string(um(T \pi))$，这显然是多项式的。 如果第一次测试成功，则进行如下操作。$T$ 中出现的 $\Sigma'$ 符号包含置换群的生成元，通过态射 $\Phi_v^T$ 计算它们的像，就可以得到所有 $v \in O$ 的 $G_v(T)$ 的生成元。因此，所有这些置换的集合 $\{\pi_1, \ldots, \pi_m\}$ 是 $G(T) = \prod_{v \in O} G_T(v)$ 的生成集，并且可以在 $T$ 的大小的多项式时间内计算出来。可以对 $\pi, \pi_1, \ldots, \pi_m$ 调用群成员关系的神谕，如果测试成功则接受。这就得到了从分层成员关系问题到群成员关系问题所需的非确定性多项式图灵归约。 由于群成员关系问题是多项式的（这是计算群论中的一个众所周知的结果），所以证明了问题 1 到 4 属于 $NP^P = NP$。 #### 2. 群约束与分层项 现在考虑群约束问题，该问题定义在群 $G < Sym(n)$ 的生成元列表和 $\{1, \ldots, n\}$ 的非空子集列表 $J_1, \ldots, J_n$ 上，询问是否存在一个置换 $\sigma \in G$ 使得 $\forall i \in \{1, \ldots, n\}, i\sigma \in J_i$。这显然是群成员关系问题的一个推广，群成员关系问题可以看作是 $J_i$ 是单元素集且两两不相交的特殊情况（即它们指定了一个唯一的置换）。 下面证明这样的群约束可以作为一个关于相当简单的分层项的成员关系问题来解决。 **定理 4**：群约束问题 $\propto$ 分层成员关系问题。 **证明**：给定由其生成元表示的群 $G$ 和 $\{1, \ldots, n\}$ 的子集 $J_1, \ldots, J_n$。在签名 $\Sigma = \{f, g, 0, 1\}$ 上构建一个分层项的成员关系问题，其中 $0, 1$ 是常量，$f, g$ 的元数为 $n$。还将使用 $\Sigma$-上下文 $c_f = f([], \ldots, [])$ 和 $c_g = g([], \ldots, [])$，以及群 $G_j = Sym(I_j)$，其中 $I_j = \{i / j \in J_i\}$。 令 $t_i = g(0, \ldots, 0, 1, 0, \ldots, 0)$，其中 $1$ 出现在 $g$ 的第 $i$ 个参数位置。类似地，令 $T_j = \langle g, c_g, G_j \rangle(0, \ldots, 0, 1, 0, \ldots, 0)$，其中 $1$ 出现在 $\langle g, c_g, G_j \rangle$ 的第 $(\min I_j)$ 个参数位置。有： $t_i \in S[T_j] \Leftrightarrow \exists \pi \in G(T_j), um(T_j^\pi) = t_i$ $\Leftrightarrow \exists \sigma \in G_j, (\min I_j)\sigma = i$ $\Leftrightarrow i \in I_j$ $\Leftrightarrow j \in J_i$ 因此，构建项 $t = f(t_1, \ldots, t_n)$ 和 $T = \langle f, c_f, G \rangle(T_1, \ldots, T_n)$。 令 $O$ 是 $T$ 的出现位置集合，$r = root(T)$，$o_j$ 是对应于 $T_j$ 的出现位置；有 $G(T) = G_T(r)G_T(o_1) \cdots G_T(o_n)$。此外，$G_T(r) = \Phi_r^T(G)$ 且 $G_T(o_j) = G(T_j)$，因此： $t \in S[T] \Leftrightarrow \exists \pi \in G(T), um(T^\pi) = t$ $\Leftrightarrow \exists \sigma \in G, \forall i, \exists \pi_i \in G(T_{i\sigma}), um(\langle f, c_f, G \rangle((T_{1\sigma})^{\pi_1}, \ldots, (T_{n\sigma})^{\pi_n})) = t$ $\Leftrightarrow \exists \sigma \in G, \forall i, \exists \pi_i \in G(T_{i\sigma}), um((T_{i\sigma})^{\pi_i}) = t_i$ $\Leftrightarrow \exists \sigma \in G, \forall i, t_i \in S[T_{i\sigma}]$ $\Leftrightarrow \exists \sigma \in G, \forall i, i\sigma \in J_i$ 从群约束问题到分层成员关系问题的这种变换显然是多项式的：$T$ 包含给定的 $G$ 的生成元，并且每个 $G_j$ 最多有两个生成元。 #### 3. 求解群约束问题是 NP 难的 并非所有的群问题都能像群成员关系问题那样在多项式时间内求解。计算群论也为许多困难的群问题提供了高效但非多项式的算法，这些问题已知是同构完全的（即与检测两个图之间的同构问题多项式等价），因此不是 NP 完全的（除非多项式层次结构坍塌到 $\Sigma_P^2