小上跨度的偏差不变性与平面性测试的复杂度

### 小上跨度的偏差不变性与平面性测试的复杂度 #### 1. 基础定义与概念 在研究小上跨度的偏差不变性相关内容时，有一系列重要的定义。 - **条件概率**：设 $\nu$ 是 $C$ 上的正概率测度，$A \subseteq \{0, 1\}^*$，$i \in N$，那么沿 $A$ 的第 $i$ 个条件 $\nu$ - 概率定义为：$\nu_A(i + 1|i) = \nu(\chi_A[0..i] | \chi_A[0..i - 1])$。 - **可和等价概率测度**：两个正概率测度 $\nu$ 和 $\nu'$ 在 $C$ 上可和等价，记为 $\nu \sim \nu'$，当且仅当对于每个 $A \subseteq \{0, 1\}^*$，有 $\sum_{i = 0}^{\infty} |\nu_A(i + 1|i) - \nu'_A(i + 1|i)| < \infty$。 - **偏差序列**： - **P - 偏差序列**：序列 $\beta = (\beta_0, \beta_1, \beta_2, \ldots)$，其中 $\beta_i \in [0, 1]$，存在函数 $\hat{\beta} : N \times N \to Q \cap [0, 1]$ 满足： - 对于所有 $i, r \in N$，$|\hat{\beta}(i, r) - \beta_i| \leq 2^{-r}$。 - 存在算法，对于所有 $i, r \in N$，能在 $|s_i| + r$ 的多项式时间（即 $\log(i + 1) + r$ 的多项式时间）内计算 $\hat{\beta}(i, r)$。 - **P - 精确偏差序列**：序列 $\beta = (\beta_0, \beta_1, \beta_2, \ldots)$，其中 $\beta_i \in Q \cap [0, 1]$，且函数 $i \to \beta_i$ 能在 $|s_i|$ 的多项式时间内计算。 - **可和等价偏差序列**：如果 $\alpha$ 和 $\beta$ 是偏差序列，它们可和等价，记为 $\alpha \sim \beta$，当且仅当 $\sum_{i = 0}^{\infty} |\alpha_i - \beta_i| < \infty$，并且显然 $\alpha \sim \beta$ 当且仅当 $\mu_{\alpha} \sim \mu_{\beta}$。 #### 2. 真值表归约 真值表归约（$\leq_{tt}$ - 归约）是有序对 $(f, g)$，对于每个 $x \in \{0, 1\}^*$，存在 $n(x) \in Z^+$ 满足： - $f(x)$ 是 $n(x)$ 元组 $(f_1(x), \ldots, f_{n(x)}(x))$ 的标准编码，其中 $f_i(x) \in \{0, 1\}^*$，这些字符串称为归约 $(f, g)$ 在输入 $x$ 上的查询，记查询集合为 $Q_{(f,g)}(x) = \{f_1(x), \ldots, f_{n(x)}(x)\}$。 - $g(x)$ 是 $n(x)$ 输入、1 输出的布尔电路的标准编码，称为归约 $(f, g)$ 在输入 $x$ 上的真值表，可将 $g(x)$ 看作布尔函数 $g(x) : \{0, 1\}^{n(x)} \to \{0, 1\}$。 真值表归约 $(f, g)$ 诱导出函数 $F_{(f,g)} : C \to C$，$F_{(f,g)}(A) = \{x \in \{0, 1\}^* | g(x)([[f_1(x) \in A]] \cdots [[f_{n(x)}(x) \in A]]) = 1\}$，同时圆柱 $C_z$ 在归约 $(f, g)$ 下的逆像为 $F_{(f,g)}^{-1}(C_z) = \{A \in C | z \subseteq F_{(f,g)}(A)\}$。 如果 $\nu$ 是 $C$ 上的概率测度，$(f, g)$ 是 $\leq_{tt}$ - 归约，那么函数 $\nu_{(f,g)} : \{0, 1\}^* \to [0, 1]$，$\nu_{(f,g)}(z) = \nu(F_{(f,g)}^{-1}(C_z))$ 也是 $C$ 上的概率测度，称为由 $\nu$ 和 $(f, g)$ 诱导的概率测度。 还有一种特殊的 $\leq_{tt}$ - 归约，即有序归约：一个 $\leq_{tt}$ - 归约 $(f, g)$ 是有序的，如果对于所有 $x, y, u, v \in \{0, 1\}^*$，若 $x < y$，$u \in Q_{(f,g)}(x)$，$v \in Q_{(f,g)}(y)$，则 $u < v$。 #### 3. 鞅收缩 给定正的抛硬币概率测度 $\nu$、有序真值表归约 $(f, g)$ 和 $\nu_{(f,g)}$ - 鞅 $d$（$\nu_{(f,g)}$ 是由 $\nu$ 和 $(f, g)$ 诱导的概率测度），可以构造 $\nu$ - 鞅 $(f, g) \hat{d}$（$(f, g)$ - 膨胀），使得当 $d$ 在 $F_{(f,g)}(A)$ 上成功时，$(f, g) \hat{d}$ 在 $A$ 上成功。这里介绍其对偶构造，即 $(f, g)$ - 收缩。 - **$(f, g)$ - 步**： - 一个正整数 $l$ 是 $(f, g)$ - 步，如果 $F_{(f,g)}(0^{l - 1}) \neq F_{(f,g)}(0^l)$。 - 对于 $k \in N$，$step(k)$ 是满足 $l \geq k$ 的最小 $(f, g)$ - 步。 - 对于 $v, w \in \{0, 1\}^*$，$v \succ w$ 表示 $w \subseteq v$ 且 $|v| = step(|w| + 1)$。 - **特殊逆函数**：定义部分函数 $F_{(f,g),d}^{-1} : \{0, 1\}^* \to \{0, 1\}^*$ 递归如下： - $F_{(f,g),d}^{-1}(\lambda) = \lambda$。 - 对于 $w \in \{0, 1\}^*$ 和 $b \in \{0, 1\}$，$F_{(f,g),d}^{-1}(wb)$ 是字典序第一个满足 $v \succ F_{