双变量单词方程与平均情况量子查询复杂度解析

### 双变量单词方程与平均情况量子查询复杂度解析 #### 双变量单词方程相关内容 1. **欧拉函数与方程基础** - 欧拉函数 $\varphi : N \to N$ 定义为 $\varphi(n) = card\{k|k$ 与 $n$ 互质 $\} = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_k})$，其中 $p_1, p_2, ..., p_k$ 是 $n$ 的所有不同质因数。函数 $\overline{\varphi}(n) = \max_{1\leq i\leq n} \varphi(i)$ 是线性的。 - 研究方程 $e_0 : XbaY = Y abX$，其解与标准单词族密切相关。 2. **方程 $e_0$ 的解** - 定义两个映射 $\alpha_1, \alpha_2 : \{a, b\}^* \times \{a, b\}^* \to \{a, b\}^* \times \{a, b\}^*$，其中 $\alpha_1(u, v) = (u, ubav)$，$\alpha_2(u, v) = (vabu, v)$。 - 引理 1 表明，$e_0$ 的解是通过以下方式得到的单词对： - 从集合 $\{(a^{n + 1}, a^n) | n \geq 0\} \cup \{(b^n, b^{n + 1}) | n \geq 0\}$ 中的一对单词 $(u, v)$ 开始。 - 对 $(u, v)$ 应用有限（可能为空）的序列 $\alpha_{i_1}, \alpha_{i_2}, ..., \alpha_{i_k}$，其中 $k \geq 0$，$1 \leq i_j \leq 2$，对于任意 $1 \leq j \leq k$。 3. **标准单词与相关引理** - 标准对集合 $R$ 是满足以下条件的最小集合： - $(a, b) \in R$。 - $R$ 在两个映射 $\beta_1, \beta_2 : \{a, b\}^* \times \{a, b\}^* \to \{a, b\}^* \times \{a, b\}^*$ 下封闭，其中 $\beta_1(u, v) = (u, uv)$，$\beta_2(u, v) = (vu, v)$。 - 标准单词集合 $S$ 定义为 $S = \{u \in \{a, b\}^* |$ 存在 $v \in \{a, b\}^*$ 使得 $(u, v) \in R$ 或 $(v, u) \in R\}$。 - 引理 2 指出，标准单词集合满足公式 $S = \{a, b\} \cup \Pi\{ab, ba\}$，其中 $\Pi = \{w \in \{a, b\}^* | w$ 有两个互质的周期 $p, q$ 且 $|w| = p + q - 2\}$。 - 引理 3 表明，对于任意 $n \geq 0$，$\#\Pi(n) = \varphi(n + 2)$。 - 引理 4 建立了 $e_0$ 的解与标准对集合 $R$ 的联系：$Sol(e_0) = \{(u, v) | (uba, vab) \in R\}$。 - 定理 2 给出： - 对于任意 $n \geq 1$，$\#L_X(e_0)(n) = \#L_Y(e_0)(n) = \varphi(n)$。 - $L_X(e_0) = L_Y(e_0) = \Pi$。 - 推论 1 得出，双变量单词方程可表达语言的非指数复杂度的线性上界是最优的。 4. **特殊方程与复杂度类型** - 研究方程中左右两边最左边出现的变量相同的双变量方程，此时另一个分量表达的语言复杂度有三种可能类型：常数型、指数型和 D1 型。 - D1 型函数定义：函数 $f : N \to N$ 是除数型，如果存在非负整数 $c_i$（$1 \leq i \leq 4$），使得 $c_1 \geq c_3$，$c_2 \geq c_4$，且 $f(k)$ 是丢番图方程 $(c_1n + c_2)m + c_3n + c_4 = k$ 的解的数量。函数 $f$ 是 D1 型，如果存在除数型函数 $g$ 使得 $f = \Theta(\overline{g})$，其中 $\overline{g}(n) = \max_{1\leq i\leq n} g(i)$。 - 引理 5 表明，如果方程 $e : \varphi = \psi$ 中 $\varphi$ 和 $\psi$ 最左边出现的变量都是 $X$，则 $\overline{\#}L_X(e)$ 是常数，$\overline{\#}L_Y(e)$ 要么是常数，要么是 D1 型，要么是指数型。 - 示例： - 方程 $e_1 : aXaY = XaY a$，$\overline{\#}L_X(e_1)$ 和 $\overline{\#}L_Y(e_1)$ 都是常数。 - 方程 $e : aXXbY = XaY bX$，$\overline{\#}L_Y(e)$ 是 D1 型。 - 方程 $e_2 : aXY Xa = XaY aX$，$\#L_Y(e_2)$ 是指数型（当 $card(\Sigma) \geq 2$ 时）。 5. **一般形式与 D2 型复杂度** - D2 型复杂度函数定义：函数 $f : N \to N$ 是除数 2 型，如果存在整数 $c_i$（$1 \leq i \leq 8$），使得 $f(k)$ 是丢番图方程 $((c_1n + c_2)m + c_3n + c_4)p + (c_5n + c_6)m + c_7n + c_8 = k$ 的解的数量。函数 $f$ 是 D2 型复杂度，如果存在除数 2 型函数 $g$ 使得 $f = \Theta(\overline{g})$，其中 $\overline{g}(n) = \max_{1\leq i\leq n} g(i)$。 - 示例：方程 $e : XabcXcbabcY = Y cbaXcbabcX$，$\#L_Y(e)$ 是 D2 型。 - 定理 3 指出，对于双变量方程 $e$，$\overline{\#}L_X(e), \overline{\#}L_Y(e) \in \{$ 常数型, D1 型, D2 型, 线性型, 指数型 $\}$。 - 定理 4 刻画了双变量单词方程可表达语言的一般形式： - 如果 $\overline{\#}L$ 是指数型，则 $L$ 包含一个模式语言。 - 如果 $\overline{\#}L$ 不是指数型，则 $L$ 是以下集合的并集： - 有限语言。 - 有限多个参数公式，如 $AnB$、$(AnB)^mAnC$ 等。 - 方程 $XAY = Y BX$ 的解。 6. **最小解与可解性** - 示例 8 中方程 $e : aXa^nbX^n = XaXbY$ 有唯一解