快速上手 Tarski 不动点问题

Posted on 2026-03-19 Edited on 2026-03-24

Abstract. 这篇综述详细调查了目前 Tarski 不动点问题的研究进展。

问题
应用
目前的结果
总结

问题

定义 1.1（Lattice）. 二元组 $(\mathscr{L}, \preceq)$ 被称为一个格，若

$\preceq$ 是 $\mathscr{L}$ 上面的偏序关系；
对于任意的 $a, b\in \mathscr{L}$，${a, b}$ 在 $\mathscr{L}$ 中有最小上界和最大下界。

称一个格是完备的，若对于任意 $S\subseteq \mathscr{L}$，$S$ 在 $\mathscr{L}$ 中有最小上界 $\sup_{\mathscr{L}} S$ 和最大下界 $\inf_{\mathscr{L}} S$。显然有限格必然完备，而譬如 $\mathbb{N}^2$ 配备自然偏序关系构成的格就不是完备的。

定义 1.2（Monotone Function）. 映射 $f: \mathscr{L}\rightarrow \mathscr{L}$ 被称为单调的，若

$$
\forall x, y, \quad x\preceq y \rightarrow f(x)\preceq f(y)
$$

定理 1.1（Tarski 不动点定理）. 设 $f$ 是完备格 $(\mathscr{L}, \preceq)$ 上的单调函数。$X^* := \{x\in X : f(x) = x\}$ 称为 $f$ 的不动点集合，其中元素称为 $f$ 的不动点，有

$X^* \ne \varnothing$；
$(X^*, \preceq)$ 是完备格。

证明. 首先构造一个集合 $X’ = \{x \in X : x \preceq f(x)\}$。注意 $X’$ 必然非空，其中一个显然的元素是 $X$ 的最小元（因 $X$ 完备必然存在）。令 $x^* = \sup_X X’$，则有：

任取 $x\in X’$ 有 $x \preceq f(x) \preceq f(x^*)$，因此 $f(x^*)$ 是 $X’$ 的上界，然而 $x^*$ 是上确界，因此有 $x^* \preceq f(x^*)$。
再迭代一轮有 $f(x^*) \preceq f(f(x^*))$，表明 $f(x^*)\in X’$，由于 $x^*$ 是 $X’$ 的上确界，必然有 $f(x^*)\preceq x^*$。

至此找到了 $x^*\in X^*$。事实上对 $X’$ 的任意一个子集都可以重复上述论证，容易得到 $X^*$ 是完备格。

$\blacksquare$

自然地我们希望能够快速计算不动点：

问题 1.1（Tarski 不动点问题）. 给定一个格 $(\mathscr{L}, \preceq)$ 和一个单调函数 $f : \mathscr{L}\rightarrow \mathscr{L}$，计算 $f$ 的任意一个不动点 $x^*$。

以及相应的判定问题：

问题 1.2（DTarski 问题）. 给定一个格 $(\mathscr{L}, \preceq)$ 和一个函数 $f : \mathscr{L}\rightarrow \mathscr{L}$，判断 $f$ 是否单调。如果单调输出一个不动点。

这个问题在计算机科学中广泛存在。比如说软件分析技术中的数据流分析算法，本质上就是在找这样一个问题的不动点。此外，Tarski 不动点问题有以下两个变种。Tarski* 问题是求解 Tarski 问题的关键子问题。

问题 1.3（Tarski* 问题）， 给定一个格 $(\mathscr{L}, \preceq)$ 和一个单调函数 $f : \mathscr{L}\rightarrow \mathscr{L}$，以及一个单调的函数 $b : \mathscr{L} \rightarrow \{-1, 0, 1\}$。求一个 $x$ 使得以下两条件之一成立：

$f(x)\preceq x \wedge b(x)\leq 0$；
$x\preceq f(x) \wedge b(x)\geq 0$。

Remark. 这个问题直接在这里提出是一个无理手。在阅读了 3.2 之后，我们会在 3.3 中阐明这个问题提出的道理。

UniqueTarski 是保证了只有唯一不动点的问题。

问题 1.4（UniqueTarski 问题）. 给定一个格 $(\mathscr{L}, \preceq)$ 和一个单调函数 $f : \mathscr{L}\rightarrow \mathscr{L}$，保证 $f$ 有且仅有一个不动点，计算该不动点 $x^*$。

我们已经学过如下结论：

定理 1.2（有限高度格上的 Query Complexity 上界）. 一个格的高度为其中最长链的长度，记作 $h(X)$。问题 1.1 存在 $O(h(X))$ 的算法。

证明. 随机从一个初始点开始迭代：令 $x^0$ 任取，$x^i = f(x^{i - 1})$，迭代直到 $x^i = x^{i + 1}$。

不失一般性设 $x^0 \prec x^1$，则根据 $f$ 的单调性可以归纳出 $x^i \preceq x^{i + 1}$。若 $h(X)$ 次迭代没有找到不动点则构造了长度为 $h(X) + 1$ 的链导致矛盾。

$\blacksquare$

注意 Grid Lattice（$[N]^d$ 在自然偏序下导出的格）的高度是 $Nd$。因此 Grid Lattice 上的 Tarski 不动点问题（记作 $\texttt{Tarski}(N, d)$）至少是 $O(Nd)$ 的。我们的最终目标是知道这个问题能不能被做到 $\mathrm{poly}(d, \log N)$。 所有的复杂度，不加额外说明都是 query complexity。

应用

这一节简单谈一下 Tarski 不动点在 TCS 中的规约，以指明我们为什么希望有 $\mathrm{poly}(d, \log N)$ 的上界。

问题 2.1（Simple Stochastic Game）. 给定一个带有一个源点 $s$ 和两个汇点 $t_0, t_1$ 的有向图 $G$，其中每个非汇点 $i$ 都恰有两条出边，记作 $j, k$，且均为 $\min$ 节点 / $\max$ 节点 / $\mathrm{rand}$ 节点之一。判断是否存在一组标号 $x_i\in [0, 1]$ 使得对于途中所有节点 $i$：

$x_i = 0$，若 $i = t_0$；
$x_i = 1$，若 $i = t_1$；
$x_i = \max(x_j, x_k)$，若 $i$ 是 $\max$ 节点；
$x_i = \min(x_j, x_k)$，若 $i$ 是 $\min$ 节点；
$x_i = \frac 12(x_j + x_k)$，若 $i$ 是 $\mathrm{rand}$ 节点。

且 $x_s \geq \frac 12$。

这个问题目前被证明是 $\mathbf{NP} \cap \mathbf{coNP}$ 的，但是不知道是不是 $\mathbf{P}$ 的。但它可以被规约到 Tarski 不动点问题，方法如下：

以精度 $1 / 2^{\mathrm{poly}(n)}$ 离散化问题。
用 Picard 迭代解方程。可以发现迭代的函数是单调的。

这里问题变成了一个 $\texttt{Tarski}(2^{\mathrm{poly}(n)}, n)$，如果能做出来 $\mathrm{poly}(d, \log N)$ 就可以证明这个问题是 $\mathbf{P}$ 的。

问题 2.2（Arrival）. 给定一个有向图 $G$，其中每个点出度至多为 $2$，两条边记作 $s_0(v)$ 和 $s_1(v)$。图上有两个特殊节点 $d, \bar{d}$，以及一个起点 $a$，考察如下过程：

令 $u = a$（从 $a$ 出发）。
令 $u’ \leftarrow s_0(u)$，交换 $s_0(u), s_1(u)$。

判断最后会走到 $d$ 还是 $\bar{d}$ 还是都不会。

这个问题由 Dohrau, Gärtner, Kohler, Matoušek, Welzl, 2016 证明了是 $\mathbf{NP} \cap \mathbf{coNP}$ 的，暂时也不知道是不是 $\mathbf{P}$ 的。然而这个问题实际上也可以转换成一个方程问题：设 $x_v$ 表示访问 $v$ 的次数，那么可以列出一个 $x_v$ 的方程组，解出来看 $x_d$ 是 $0$ 还是 $1$ 即可。

这个方程也可以 Picard 迭代。而且这个过程如果要终止，必然在 $n2^n$ 轮内终止（总共状态数只有这么多种，没结束表明陷入循环）。因此这归约到了 $\texttt{Tarski}(n2^n, n)$。

目前的结果

$\texttt{Tarski}(N, 2)$ 的紧下界

可以证明 $\texttt{Tarski}(N, 2)$ 是 $\Omega(\log^2 N)$ 的。方法是在 Hard Instance 上面做 Adversarial Argument。

构造的 Hard Instance 主要是以下形式：

首先取一条左上角到右上角的路径（只能向右或者向上走）；
在这条路径上构造一个一维的 Binary Search 问题；
对于其余格点，路径上方的指向其右下方，路径下方的指向其左上方。

一个例子如下。容易证明这样的构造都是单调的。

在这些 Hard Instance 上证明结论的手法非常显然。直觉是：

根据 Binary Search Lowerbound，至少要问到“路径”上的 $O(\log n)$ 个点才行；
找到路径上的任意一个点都是困难的（至少需要 $O(\log n)$ 次询问）。

Remark. 证明的时候有一些细节，想不出来可以去看 1909.03210，这里不多赘述。感觉有一个要点就是证这种对数复杂度的东西边界太复杂可以直接根号分治，反正 $\log \sqrt N$ 还是 $\log N$。

$\texttt{Tarski}(N, d)$ 的 $O(\log^d N)$ 算法

先考虑 $\texttt{Tarski}(N, 1)$。

观察 3.2.1. 对于任意的 $x\in [N]$，若 $f(x) \leq x$，则 $x$ 左边有不动点，否则 $x$ 右边有不动点。

这给出了显然的二分，因此 $T(N, 1) = O(\log N)$。

观察 3.2.2. 考虑 $\texttt{Tarski}(N, d)$（$d\geq 2$）。固定 $y\in [N]$，对于任意的 $\boldsymbol{x}\in [N]^{d - 1}$，记 $f(\boldsymbol{x}, y) = (f^0(\boldsymbol{x}), f^1(y))$。则 $f^0$ 是 $[N]^{d - 1}$ 上的单调函数，因此求 $f^0(\boldsymbol{x})$ 的不动点是 $\texttt{Tarski}(N, d - 1)$ 问题。

观察 3.2.3. 对于任意的 $\boldsymbol{x}\in [N]^{d - 1}, y\in [N]$。若 $f(\boldsymbol{x}, y) = \boldsymbol{x}, y’$，其中 $y’ \leq y$，则 $\{(\boldsymbol{x}’, y’) : \boldsymbol{x}’\preceq \boldsymbol{x}, y’ \leq y\}$ 中有不动点，否则 $\{\boldsymbol{x}’, y’ : \boldsymbol{x}\preceq \boldsymbol{x}’, y\leq y’\}$ 中有不动点。

这给出了递归的方案。每次将整个 Grid 拦腰切断，然后找截面上的（投影）不动点，根据这个点的指向判断不动点在上半部分还是下半部分。切成平面之后就实现了降维。因此有

$$
T(N, d) = \log N\cdot T(N, d - 1) + T(N, d - 1) = O(\log^d N)
$$

$\texttt{Tarski}(N, k)$ 和 $\texttt{Tarski}^*(N, k)$ 的联系

3.2 节给我们的启发是，拦腰切断一个超立方体后，可以在截面上找到一个点，依据这个点缩小问题规模。但是 3.2 找到的那个点满足的条件明显过强了。事实上，我们能够将向“左下角”或者“右上角”递归的充分条件松驰成：

观察 3.3.1. 设 $\mathscr{L}_s = \{\boldsymbol{x} : x_i = s\}$ 是 $\mathscr{L} = [N]^k$ 的一个截面，$\boldsymbol{x}_s$ 表示 $\boldsymbol{x}$ 限制在这个截面上的坐标。则截面上必然至少存在一个点 $\boldsymbol{x}$ 满足以下两个条件之一：

$\boldsymbol{x}_s \preceq f(\boldsymbol{x})_s$ 且 $s \leq f(\boldsymbol{x})_i$；

$f(\boldsymbol{x})_s \preceq \boldsymbol{x}_s$ 且 $f(\boldsymbol{x})_i \leq s$。

这个观察的证明是相当容易的，因为观察 3.2.2 给出的那个不动点就是一个满足这个条件的点。而这个问题就是 $\texttt{Tarski}^*(N, k - 1)$（$g$ 指示了 $f(\boldsymbol{x})_i \prec x_i$ / $f(\boldsymbol{x})_i = x_i$ / $s\prec f(\boldsymbol{x})_i$）！

观察 3.3.2. 设 $\boldsymbol{x}$ 是符合观察 3.3.1 条件的一个点。若它满足的是条件 1，则 $\{\boldsymbol{x}’ \in \mathscr{L} : \boldsymbol{x} \preceq \boldsymbol{x}’\}$ 中有不动点；若它满足的是条件 2，则 $\{\boldsymbol{x}’ \in \mathscr{L} : \boldsymbol{x}’ \preceq \boldsymbol{x}\}$ 中有不动点。

至此我们知道了调用一次 $\texttt{Tarski}^*$ oracle 可以将一个维度的问题规模砍一半。仅需 $k \log N$ 次 oracle 调用就可以将每一维的大小砍到 $\leq 2$，然后用那个平凡的迭代算法去 $O(k)$ 求解这个边界即可。以上结果归结为以下定理：

定理 3.3.1. 若算法 $\mathcal{A}$ 能在 $q(n, k)$ 时间内解决 $\texttt{Tarski}^*(N, k)$，则存在算法在以下时间复杂度内解决 $\texttt{Tarski}(N, k + 1)$：

$$
O(k + k\log n\cdot q(n, k))
$$

这里我们定义两个集合以备后续使用：

定义 3.3.1（Upset，Downset）. 定义

$$
\begin{aligned}
& \mathrm{Upset}_f(\mathscr{L}) := \{\boldsymbol{x}\in \mathscr{L} : f(\boldsymbol{x})\preceq \boldsymbol{x}\} \\
& \mathrm{Downset}_f(\mathscr{L}) := \{\boldsymbol{x}\in \mathscr{L} : \boldsymbol{x} \preceq f(\boldsymbol{x})\}
\end{aligned}
$$

$\texttt{Tarski}^*$ 的任务就是在截面上任意找一个 Upset 或者 Downset 的元素。需要熟记的是若 $\boldsymbol{d}\preceq \boldsymbol{u}$ 满足 $\boldsymbol{d}\in \mathrm{Downset}_f(\mathscr{L})$ 且 $\boldsymbol{u}\in \mathrm{Upset}_f(\mathscr{L})$，则 $f$ 封闭于 $\{\boldsymbol{x}\in \mathscr{L} : \boldsymbol{d}\preceq \boldsymbol{x} \preceq \boldsymbol{u}\}$ 中，因此这个子集中有不动点。

$\texttt{Tarski}(N, 3)$ 的 $O(\log^2 N)$ 算法

Fearnley, Pálvölgyi, Savani, 2021 提出了一个 $O(\log N)$ 求解 $\textsf{Tarski}^*(N, 2)$ 的算法，据此给出了 $\texttt{Tarski}(N, 3)$ 的 $O(\log^2 N)$ 算法。关于这个问题，折叠部分的尝试是很有启发性的，读者可以阅读这段文字或者自行领悟这个算法的思路。

一些可能有启发的推理.

读者可以自行尝试一下取中点分治然后分类讨论。设中点为 $\boldsymbol{m}$，右边界的中点为 $\boldsymbol{r}$。

若 $f(\boldsymbol{m})_1 \leq m_1, f(\boldsymbol{m})_2 \leq m_2$. 则 $f$ 限制在 $\{\boldsymbol{x}\in \mathscr{L} : \boldsymbol{x}\preceq \boldsymbol{m}\}$ 上是封闭的，其中必存在解，可以递归；
若 $f(\boldsymbol{m})_1 > m_1, f(\boldsymbol{m})_2 > m_2$. 则 $f$ 限制在 $\{\boldsymbol{x} \in \mathscr{L} : \boldsymbol{m}\preceq \boldsymbol{x}\}$ 上是封闭的，其中必存在解，可以递归；
剩下两种情况对称。不失一般性地，若 $f(\boldsymbol{m})_1 > m_1, f(\boldsymbol{m})_2 \leq m_2$. 此时再考虑 $g(\boldsymbol{m})$ 的情况：
1. 若 $g(\boldsymbol{m}) \geq 0$. 则 $g$ 限制在 $\{\boldsymbol{x}\in \mathscr{L} : \boldsymbol{m}\preceq \boldsymbol{x}\}$ 上都非负。现在考虑 $\boldsymbol{r}$ 的情况：
  1. 若 $f(\boldsymbol{r})_2 \leq r_2$，则 $f$ 限制在 $\{\boldsymbol{x}\in \mathscr{L} : \boldsymbol{x} \preceq \boldsymbol{r}\}$ 上封闭，可以递归；
  2. 若 $f(\boldsymbol{r})_2 > r_2$，则根据单调性在 $\boldsymbol{mr}$ 这一条水平线段上，存在一个临界点 $(t, r_2)$ 使得 $f((t, r_2))_2 \leq r_2$ 且 $f((t + 1, r_2)) > r_2$。
    1. 若 $f((t, r_2))_1 \leq t$，则 $f$ 限制在 $\{\boldsymbol{x}\in \mathscr{L} : \boldsymbol{x}\preceq (t, r_2)\}$ 上封闭，可以递归；
    2. 否则，$f((t, r_2))_1 > t$，因此 $f((t + 1, r_2))_1 \geq t$，$(t + 1, r_2)$ 是问题的一个解。
2. …
…

自然，你这个分类讨论可以跑通。但现在以下复杂度的优化空间和 $f$ 的封闭性见合：

保持整个递归的不变量（$f$ 封闭）不变，上面的递归必然要用一次二分来找到 $t$，复杂度多一个 $\log$ 因子。
注意上面的 Case 3.1.1，3.1.2.1 和 3.1.2.2 都指示 $\{\boldsymbol{x} \in \mathscr{L} : \boldsymbol{x} \preceq \boldsymbol{r}\}$ 这个范围内有解。如果直接往里面递归，复杂度还是单 $\log$，代价是 $f$ 现在不再封闭于目标区间。

所幸我们递归时需要的最低限度的要求是 $\texttt{Tarski}^*$ 问题在目标格上面有解，而非 $f$ 封闭。一些弱得多的条件，比如已知限制在 $\mathscr{L}$ 的一个局部上 $f$ 封闭，就可以保证这个要求。这暗示着放弃 $f$ 的封闭性来追求更快的算法的可能性。

考虑状如上方 Case 3.1.2 中线段 $\boldsymbol{mr}$ 的两个端点的性质实际上给出了一个解或者一个限制在截面上的 Upset 元素，我们管这种线段叫做 Upset Witness（USW）。对称的情况也一并考虑。具体地，我们定义：

定义 3.4.1（Witnesses）. 两个点 $\boldsymbol{d} \preceq \boldsymbol{u}$ 被称为一组 Witness，若以下两条件之一成立：

$d_1 = u_1$ 且 $f(\boldsymbol{d})_2 \geq d_2, f(\boldsymbol{u})_2 \leq u_2$；
$d_2 = u_2$ 且 $f(\boldsymbol{d})_1 \geq d_1, f(\boldsymbol{u})_1 \geq u_1$。

对于一个 Witness $(\boldsymbol{d}, \boldsymbol{u})$，若：

$g(\boldsymbol{d})\geq 0\wedge g(\boldsymbol{u}) \geq 0$，则称为 Upset Witness；
$g(\boldsymbol{u})\leq 0\wedge g(\boldsymbol{u}) \leq 0$，则称为 Downset Witness。

然后我们定义如下的递归不变量：称 $\boldsymbol{d} \preceq \boldsymbol{u}$ 框出的子问题满足递归不变量以下条件之一成立：

$\boldsymbol{d} \in \mathrm{Downset}_f(\mathscr{L})$ 且 $\boldsymbol{u}\in \mathrm{Upset}_f(\mathscr{L})$；
$\boldsymbol{d} \in \mathrm{Downset}_f(\mathscr{L})$ 且 $(\boldsymbol{b}, \boldsymbol{u})$ 是 Upset Witness 且 $\boldsymbol{d}\preceq \boldsymbol{b}$；
$(\boldsymbol{d}, \boldsymbol{a})$ 是 Downset Witness 且 $\boldsymbol{u}\in \mathrm{Upset}_f(\mathscr{L})$ 且 $\boldsymbol{a}\preceq \boldsymbol{u}$；
$(\boldsymbol{d}, \boldsymbol{a})$ 是 Downset Witness 且 $(\boldsymbol{b}, \boldsymbol{u})$ 是 Upset Witness 且 $\boldsymbol{a}\preceq \boldsymbol{b}$。

显然，如果子问题满足递归不变量，则其中必然有解。读者不妨自行分类讨论这个递归不变量下可能的诸多情况然后得到 $O(\log n)$ 的算法。

高维 Tarski 问题的分解引理

定理 3.4.1（Theorem 18 of Fearnley, Pálvölgyi, Savani, 2021）. 若存在一个算法 $\mathcal{A}$ 用 $q(n, a)$ 次询问解决 $\texttt{Tarski}(n, a)$，一个算法 $\mathcal{B}$ 用 $q(n, b)$ 次询问解决 $\texttt{Tarski}(n, a)$，则存在一个算法 $\mathcal{L}$ 用 $O(q(n, a)\cdot q(n, b))$ 次询问解决 $\texttt{Tarski}(n, a + b)$。

证明. 考虑一个 $a + b$ 维的格 $\mathscr{L} = \mathscr{L}_a\times \mathscr{L}_b$。我们用 $(\boldsymbol{x}, \boldsymbol{y})$ 表示其中的元素。首先为了利用 $\mathcal{A}$ 这个算法，你至少要有一个 $\mathscr{L}_a$ 上面的 oracle 才行。此外还要让这个函数的输出和 $f$ 产生关系，你需要将输入 $\boldsymbol{x}$ 补充成一对 $\boldsymbol{x}, \boldsymbol{y}$，不难想到这个 $\boldsymbol{y}$ 要从 $\mathcal{B}$ 中寻找。注意，固定 $\boldsymbol{x}$，我们得到了一个低维超平面，便有 $f$ 在这个超平面上的投影

$$
f_{\boldsymbol{x}}(\cdot)_i = f((\boldsymbol{y}), \cdot)_{i + a}
$$

这给出了一个最直接的 $\mathcal{L}_a$ 上的函数 $f$ 的（错误的）oracle 的构造：

对于输入的 $\boldsymbol{x}$，用 $\mathcal{B}$ 找 $f_{\boldsymbol{x}}(\cdot)$ 的不动点 $\boldsymbol{y}^*$；
返回 $f(\boldsymbol{x}, \boldsymbol{y}^*)$。

之所以说这个 oracle 是错误的，因为单调性完全得不到保证。因此，动态地维护构造的 oracle 的单调性成了眼见的要点。最简明的方法的来自于以下的思路：

假设你现在已经使用了 $\mathscr{P} \subset \mathscr{L}_a\times \mathscr{L}_b$ 中的点。具体地，$\mathscr{P}$ 中有 $(\boldsymbol{x}, \boldsymbol{y})$ 若：你曾向欲构造的 oracle 提交查询 $\boldsymbol{x}$，此时为了构造一个 $f$ 的输入，你用 $\mathcal{B}$ 找了某个 $\boldsymbol{y}$，然后返回了 $f((\boldsymbol{x}, \boldsymbol{y}))$。
现在，你又收到了一个 oracle 查询 $\boldsymbol{x}$。为了不产生矛盾，有两个集合值得关注：
- 集合 $\mathscr{D} := \{\boldsymbol{y}’ : \exists (\boldsymbol{x}’, \boldsymbol{y}’)\in \mathscr{P}, \boldsymbol{x}’\preceq \boldsymbol{x}\}$。你返回的 $f(\boldsymbol{x}, \boldsymbol{y})$ 必须满足 $f(\boldsymbol{x}’, \boldsymbol{y}’) \preceq f(\boldsymbol{x}, \boldsymbol{y})$。
- 集合 $\mathscr{U} := \{\boldsymbol{y}’ : \exists (\boldsymbol{x}’, \boldsymbol{y}’)\in \mathscr{P}, \boldsymbol{x}\preceq \boldsymbol{x}’\}$。你返回的 $f(\boldsymbol{x}, \boldsymbol{y})$ 必须满足 $f(\boldsymbol{x}, \boldsymbol{y}) \preceq f(\boldsymbol{x}’, \boldsymbol{y}’)$。
为了保证这个性质，我们利用 $f$ 函数的单调性，让 $\boldsymbol{y}$（自变量）介于 $l := \sup \mathscr{D}$ 和 $u := \inf \mathscr{U}$ 之间即可。我们用算法 $\mathcal{B}$ 去找 $f_{\boldsymbol{x}}(\cdot)$ 在 $\mathscr{L}_{l, u} := \{\boldsymbol{y} : \sup \mathscr{D} \leq \boldsymbol{y} \leq \inf \mathscr{U}\}$ 上的不动点 $\boldsymbol{y}^*$。

显然，如果上面的 oracle 构造中，只要 $\mathcal{B}$ 能一直找到不动点，$\mathcal{A}$ 运行结束之后就会找到 $\mathscr{L}$ 的不动点。而这个东西的证明分成两部分：

观察 3.4.1. 上述算法 $\mathcal{A}$ 运行并调用我们构造的这个 oracle 的过程中，始终有 $l \preceq u$。

这个观察源于完备格上显然的结论：对于完备格的两个子集 $\mathscr{S}, \mathscr{T}$，若对于任意的 $x\in \mathscr{S}, y\in \mathscr{T}$ 都有 $x\preceq y$，则 $\sup \mathscr{S}\preceq \inf \mathscr{T}$。具体证明读者不妨自己根据维护 $\mathscr{P}$ 的过程分类讨论。

观察 3.4.2. 上述算法 $\mathcal{A}$ 运行并调用我们构造的这个 oracle 的过程中，$f(\mathscr{L}_{l, u}) \subseteq \mathscr{L}_{l, u}$ 始终成立。

这源于上确界、下确界的定义。读者可以自行验证。

至此我们扫除了证明定理 3.4.1 的全部障碍，查询的复杂度也是容易算的。

$\blacksquare$

根据此前的结果，推广到高维有

推论 3.4.1. $\texttt{Tarski}(N, k)$ 有 $O(\log^{2\left\lceil d / 3\right\rceil + 1} n)$ 的算法。

当然这个推论不是 SOTA，因为对于 Tarski* 问题也有类似结果。

定理 3.4.2（Theorem 3 of Chen, Li, 2022）. 若存在一个算法 $\mathcal{A}$ 用 $q(n, a)$ 次询问解决 $\texttt{Tarski}^*(n, a)$，一个算法 $\mathcal{B}$ 用 $q(n, b)$ 次询问解决 $\texttt{Tarski}^*(n, b)$，则存在一个算法用 $O((b + 1) \cdot q(n, a)\cdot q(n, b))$ 次询问解决 $\texttt{Tarski}^*(n, a + b)$。

证明. 【FIXME】

根据定理 3.4.2 和 $\texttt{Tarski}^*(N, 2)$ 的 $O(\log n)$ 算法可以得到以下推论：

推论 3.4.2. $\texttt{Tarski}(N, k)$ 有 $O(k\log^{\left\lceil n / 2\right\rceil + 1}n)$ 的算法。

到这里可以知道给出低维 Tarski 问题的高效算法可以改进指数上的 dependence，但至于怎么把 $k$ 拉下来还是 open 的。

$\textsf{Tarski}(N, 4)$ 的 $O(\log^2 N)$ 算法

【FIXME】

$\textsf{Tarski}$ 和 $\textsf{UniqueTarski}$ 的关系

事实上，Tarski 和 Unique Tarski 很可能“一样难”，这些结果均由 Chen, L., Yannakakis, 2023 给出。主要是

定理 3.7.1. 若算法 $\mathcal{A}$ 能够解决 $\texttt{UniqueTarski}(N, d)$，则它可以以相同的 query complexity 解决 $\texttt{Tarski}(N, d)$。

证明. 【FIXME】

定理 3.7.2. 若存在 $\texttt{Tarski}$ 到 $\texttt{UniqueTarski}$ 的有效标准规约（efficient standard reduction），则 $\texttt{Tarski}(N, d)$ 有 $\mathrm{poly}(d, \log N)$ 的算法。

证明. 【FIXME】讲道理我现在连这个在说什么都没看懂。

$\textsf{Tarski}(N, k)$ 的一个下界

定理 3.8.1（Theorem 1 of Branzei, Phillips, Recker, 2025）. $\textsf{Tarski}(n, k)$ 的随机算法有复杂度下界

$$
\Omega\left(k + \frac{k\log n}{\log k}\right)
$$

这篇文章构造了一族 Hard Instance：

定义 3.8.1（Definition 2 of Branzei, Phillips, Recker, 2025）. 对于任意的 $\boldsymbol{a}\in \mathscr{L}$（$\mathscr{L} = [N]^k$），$\boldsymbol{a}$ 诱导出一个函数 $f^{\boldsymbol{a}}$：

$$
f^{\boldsymbol{a}}(\boldsymbol{v})_i = \begin{cases}
v_i - 1 & \text{if $v_i > a_i$ and $\forall j < i, v_j \leq a_j$} \\
v_i + 1 & \text{if $v_i < a_i$ and $\forall j < i, v_j \geq a_j$} \\
v_i & \text{otherwise.}
\end{cases}
$$

类 $\mathcal{F}_n^k = \{ f^{\boldsymbol{a}} : \boldsymbol{a}\in [N]^k \}$ 是全体这样函数的集合。

这是一个单调函数，而且只有唯一的不动点 $\boldsymbol{a}$。对于这个函数我目前只有最低程度的直观，就是它要让所有点汇聚于 $\boldsymbol{a}$，因此把每个点第一个过低或者过高的位置往回拉。

定理 3.8.1 的证明主要分成以下三个部分。这里涉及到一些随机算法下界证明，我不是很熟悉相关工具因此还不会证明。

命题 3.8.1. $\textsf{Tarski}(2, k)$ 的随机算法复杂度下界是 $\Omega(k)$。

证明. 【FIXME】。

命题 3.8.2. 对于 $N\geq 2$ 有 $\textsf{Tarski}(2, k) \leq_p \textsf{Tarski}(N, k)$。

证明. Trivial。

命题 3.8.3. $\textsf{Tarski}(N, k)$ 的随机算法复杂度有下界 $\Omega\left(\frac{k\log n}{\log k}\right)$。

证明. 【FIXME】。

可见现在给出的关于 Tarski 不动点问题关于 $n$ 的下界最大仅为 $\log^2 n$。当前还没有找到哪个维度中下界是 $\Omega(\log^3 N)$ 的。

针对 $\mathcal{F}_n^k$ 的 $O(\sqrt k\log n)$ 量子算法

本节我们将给出针对 $\mathcal{F}_n^k$ 的量子平方加速。注意 Hard Instance 中，似乎自变量蕴含了它诸位和 $\boldsymbol{a}$ 的大小关系信息。此时，一个值得尝试的方向是对所有维度同时进行二分：我们希望实现一个算法，给定阈值 $\boldsymbol{m} \in [N]^k$，知道这样一个字符串 $\boldsymbol{b}\in \{0, 1\}^k$ 的内容：

$$
b_i = \mathbf{1}\{a_i < m_i\}
$$

现在假设我们有对函数 $f$ 的 unitary oracle access $\mathrm{O}_f$，按照惯例假设成：

$$
\mathrm{O}_f|\boldsymbol{v}\rangle|\boldsymbol{z}\rangle = |\boldsymbol{v}\rangle|\boldsymbol{z} + f(\boldsymbol{v})\rangle
$$

此处 $+$ 系指 $\mathbb{Z}_N^k$ 下的加法。因为 $f$ 的结构良好，不妨考察给 $|\boldsymbol{v}\rangle| -\boldsymbol{v}\rangle$ 作用一个 $\mathrm{O}_{f^{\boldsymbol{a}}}$ 会发生什么。

$$
\mathrm{O}_{f^{\boldsymbol{a}}}|\boldsymbol{v}\rangle|-\boldsymbol{v}\rangle = |\boldsymbol{v}\rangle|g^{\boldsymbol{a}}(\boldsymbol{v})\rangle
$$

其中

$$
g^{\boldsymbol{a}}(\boldsymbol{v}) = \begin{cases}
- 1 & \text{if $v_i > a_i$ and $\forall j < i, v_j \leq a_j$} \\
+ 1 & \text{if $v_i < a_i$ and $\forall j < i, v_j \geq a_j$} \\
0 & \text{otherwise.}
\end{cases}
$$

直接调用 $g^{\boldsymbol{a}}(\boldsymbol{m})$，可以得到以下观察：

如果存在某个 $b_i = 1$，则序列里必有 $-1$；
如果存在某个 $b_i = 0$，则序列里必有 $0$ 或者 $+1$。

换言之，我们可以检查 $\boldsymbol{b}$ 是否为全 $0$ 或者全 $1$。对量子搜索算法有研究者可能容易想到下面的这一条思路：

观察 3.9.1. 利用 $O(1)$ 次上述 oracle 访问，可以检查 $\boldsymbol{b}$ 的任意一个子序列是否是全 $0$、是否是全 $1$。

假设这个子序列是 $S\subseteq [k]$。我们取

$$
m’_i = \begin{cases}
m_i & i\in S \\
0 & i\notin S
\end{cases}
$$

则查询 $\mathrm{O}_{f^{\boldsymbol{a}}}|\boldsymbol{m}’\rangle|-\boldsymbol{m}’\rangle$ 所得第二个 register 中有 $-1$ 表明 $\boldsymbol{b}_S$ 不是全 $0$。全 $1$ 的检查类似。

观察 3.9.2. 利用 $O(1)$ 次上述 oracle 访问，可以检查 $\boldsymbol{b}$ 的任意一个子序列 $\boldsymbol{b}_S$ 是否等于 $\boldsymbol{y}$（$|\boldsymbol{y}| = |S|$）。

只需检查 $\boldsymbol{b}_S$ 中 $0$ 的部分是否全是 $0$，$1$ 的部分全是 $1$ 即可。

至此我们搭建了一个 search with wildcard oracle。回忆

问题 3.9.1（search with wildcard problem）. 有一个长度为 $N$ 的隐藏的字符串 $\boldsymbol{b}\in \{0, 1\}^N$。给定 $b$ 的如下 oracle 访问：给定 $S\subseteq [N]$ 和字符串 $\boldsymbol{y}\in \{0, 1\}^{|S|}$，有

$$
\mathrm{O}_{\boldsymbol{b}} |S\rangle|\boldsymbol{y}\rangle|z\rangle = |S\rangle|\boldsymbol{y}\rangle|z \oplus \mathbf{1}\{\boldsymbol{b}_S = \boldsymbol{y}\}\rangle
$$

求 $\boldsymbol{b}$。

关于这个问题，有以下结果：

Ambainis, Montanaro, 2014（1210.1148）证明了存在 query complexity $O(\sqrt n\log n)$ 的量子算法；
这个问题明显不弱于 Grover Search，因此存在 query complexity 为 $\Omega(\sqrt n)$ 的下界；
Cornelissen, Mande, Patro, Raja, and Sanyal, 2025（2511.04669）证明了存在 $O(\sqrt n)$ 的量子算法。

因此二分的判定有 $O(\sqrt k)$ 的算法。这样做并行二分，query complexity 实为 $O(\sqrt k \log N)$，我们实现了近乎平方的量子加速。

总结

现在这个题的 Quantum 基本上没什么人做过。不知道有什么突破点，可能包括：

量子算法对二分没有加速。可能 $k$ 比较小的时候可以证下界。不知道对着 $\texttt{Tarski}(N, 2)$ adversary 一下有没有用？
量子算法可以解决高维情况下的经典 hard instance，说不定有希望？但是那个 hard instance 太特殊了。
好像在这个问题上对所有维度一起二分有 work 的希望？但好像这个题在 hard instance 外面又不是什么二分。
量子算法还有一个潜在的优势就是搞多叉分治，不知道这个题有没有类似的东西？
有没有可能量子算法有别的分解引理？