指针追逐通信问题

在第 $t$ 步，只有持有当前顶点所在侧函数的一方知道下一指针。Alice 从 $v_0\in V_A$ 开始恰好知道第一步；若 Bob 被迫首发，他尚不知道 $v_1=f_A(v_0)$，第一条消息很难针对真正路径。随机协议可预先发送某个抽样顶点集的指针，以概率命中后“赶回进度”，但抽样集太小就很可能错过整条路径。

下界跟踪协议树矩形中尚未暴露的随机函数值：短消息只能稍微偏斜大量独立指针的条件分布，沿路径累积的偏斜受信息论估计控制。轮消除公理库轮消除引理Round elimination lemma · MNSW round elimination在 indexed direct-sum 问题中证明 Alice 的短首消息对未知目标坐标信息很少，从而删去一条消息并交换起始方。把同一种“未知目标导致首消息低信息”现象抽象成可迭代模板；上面的精确 $n/k^2-k\log n$ 则来自 Nisan–Wigderson 针对本问题的原始分析。

取 $V_A=\{a_0,a_1,a_2,a_3\}$、$V_B=\{b_0,b_1,b_2,b_3\}$，$v_0=a_0$，并设

则三步轨迹为

所以 $g_3=b_3$。Alice 先说时依次发送 $b_2,a_1,b_3$ 即完成；Bob 先说时，他的首消息在不知道 $b_2$ 的情况下必须同时为四个潜在 $f_A(a_0)$ 服务。这是 wrong-starter 障碍的最小可追踪实例。

参数边界不能省略负项：当 $k$ 接近 $n^{1/3}$ 以上时，$n/k^2-k\log n$ 可不再给正的有用界。输出完整顶点与只输出 parity 的上界差一个输出长度 convention，但原论文说明下界可保留到 Boolean 版本。把双方函数都给同一方、允许每轮双向同时发消息或改成 private coins，都会改变模型。

指针追逐是 round hierarchy 的规范分离：相同函数、相同总输入长度，仅改变消息数或首发者就产生指数级差距。它还能经 streaming、distributed computation 和 cell-probe 归约，把“每次只能沿一条依赖链获得下一地址”的限制转为 pass、round 或 probe 下界。

该问题不是单靠总通信矩形参数就能完整描述；协议的时间顺序决定某条消息发出时谁已知道当前顶点。因而它为轮数—通信量权衡公理库轮数—通信量权衡Round-communication tradeoff · Round-sensitive communication complexity固定消息条数、首发者、单消息预算与错误后，刻画增加交互如何降低完成同一通信任务的总 bit 数。提供具体基准，也展示 round-insensitive LP 即使给出总量下界，也可能看不见首发方向的巨大差异。