非均匀族计数的力量

# 非均匀族计数的力量 ## 1. 引言 计数在理论计算机科学中是一个重要的研究课题。本文聚焦于多项式规模有限自动机族的非均匀模型中的“计数”问题，深入探讨了不同计数复杂度类之间的关系。 ## 2. 基本引理 ### 2.1 引理 4 对于任意具有内部状态集 $Q_M$ 的 1nfa $M$，存在另一个具有内部状态集 $Q_N$ 的 1nfa $N$，使得对于任意 $x$，若 $\#M(x) = \#M(x)$，则 $\#N(x) = \#N(x)$；若 $\#M(x) \neq \#M(x)$，则 $\#N(x) < \#N(x)$，并且 $|Q_N| \leq 2|Q_M|$。 ### 2.2 复杂度类关系 复杂度类 $1C=$ 和 $1SP$ 分别与 $co - 1N$ 和 $1U$ 密切相关，因为后两个类是通过将前两个类定义中的 $1Gap$ 替换为 $1\#$ 直接得到的。 ## 3. 计数复杂度类之间的关系 ### 3.1 基本闭包性质 - **补运算闭包**：$co - 1P$ 与 $1P$ 重合，并且 $1\oplus = co - 1\oplus$，$1SP = co - 1SP$。 - **交并运算闭包**：$1N$ 在交和并运算下封闭，但在补运算下不封闭；$1C=$ 在交运算下封闭，$co - 1C=$ 在并运算下封闭。 - **同态闭包**：$1\#$ 在同态和非擦除前缀自由同态的逆运算下封闭。 | 复杂度类 | 补运算 | 交运算 | 并运算 | 同态 | 非擦除前缀自由同态的逆 | | ---- | ---- | ---- | ---- | ---- | ---- | | $1P$ | 封闭 | - | - | - | - | | $1\oplus$ | 封闭 | - | - | - | - | | $1SP$ | 封闭 | - | - | - | - | | $1N$ | 不封闭 | 封闭 | 封闭 | - | - | | $1C=$ | 不封闭 | 封闭 | - | - | - | | $co - 1C=$ | - | - | 封闭 | - | - | | $1\#$ | - | - | - | 封闭 | 封闭 | ### 3.2 复杂度类 $1U$ - **包含关系**：$1U \subseteq 1SP$ 且 $co - 1U \subseteq 1SP$，并且这些包含关系是严格的，即 $1U \subsetneq 1SP$。 - **证明思路**： - 对于 $1U \subseteq 1SP$ 的证明，设 $L = \{(L^{(+)}_{n}, L^{(-)}_{n})\}_{n\in N}$ 是 $1U$ 中的任意族，取多项式规模的 1nfa 族 $M = \{M_n\}_{n\in N}$ 来解决 $L$，其中每个 $M_n$ 至少在 $\Sigma(n) = L^{(+)}_{n} \cup L^{(-)}_{n}$ 上是无歧义的。构造 1nfa $N_n$ 来解决 $L$：在 $x$ 上模拟 $M_n$，若 $M_n$ 进入接受状态，$N_n$ 也进入接受状态；若 $M_n$ 进入拒绝状态，$N_n$ 分支为两条计算路径，一条接受，一条拒绝。 - 对于 $1U \neq 1SP$ 的证明，定义 $L^{(+)}_{n} = \{x\#y \in T_n | \#0(x) = \#0(y) + 1\}$，$L^{(-)}_{n} = \{x\#y \in T_n | \#0(x) = \#0(y)\}$，$T_n = \{x\#y | x, y \in \{0, 1\}^{2n}\}$，并设 $L_{sp} = \{(L^{(+)}_{n}, L^{(-)}_{n})\}_{n\in N}$，可以证明 $L_{sp} \in 1SP$ 但 $L_{sp} \notin 1U$。 - **类分离**：$co - 1U \nsubseteq 1N$。 ### 3.3 复杂度类 $1C=$ - **类分离关系**： - $1N \subsetneq co - 1C=$ 且 $co - 1N \subsetneq 1C=$。 - $1C= \nsubseteq 1N$ 且 $1N \nsubseteq 1C=$。 - **非闭包性质**：$1C=$ 在补运算下不封闭。 - **证明思路**： - 为证明上述类分离关系，需要用到引理 12。设 $\{(L^{(+)}_{n}, L^{(-)}_{n})\}_{n\in N}$ 是字母表 $\Sigma$ 上 $1C=$ 中的任意族，存在多项式 $p$ 满足：对于任意 $n$ 和 $l$（$l \leq n - 1$），$z \in \Sigma^l$，$A_{n,l,z} = \{x \in \Sigma^{n - l} | xz \in L^{(+)}_{n}\}$，存在子集 $S \subseteq A_{n,l,z}$ 且 $|S| \le