高效输出时间下通信协议的扩展公式

### 高效输出时间下通信协议的扩展公式 #### 1. 引言 线性扩展公式是整数规划和组合优化中的基础工具，它能将多面体 $P$ 上的优化问题简化为线性投影到 $P$ 的多面体 $Q$ 上的类似问题。当 $Q$ 能用比 $P$ 少得多的不等式描述时（通常在 $P$ 的维度上，$Q$ 是多项式级，$P$ 是指数级），就能实现计算加速。$Q$ 被称为 $P$ 的扩展，描述 $Q$ 的一组线性不等式就是扩展公式，$P$ 的扩展公式中最少的不等式数量被称为 $P$ 的扩展复杂度，记为 $xc(P)$。近年来，计算或界定多面体的扩展复杂度一直是重要的研究课题。 扩展复杂度的下界通常是无条件的，既不依赖于任何复杂度理论假设，也不考虑产生扩展所需的时间或不等式中系数的编码长度。而上界常常是构造性的，能在其大小的多项式（通常是线性）时间内产生扩展公式，例如 Balas 的多面体并集、反射关系和分支多面体分支系统。 能够高效构造扩展公式至关重要，因为其最终目标是让某些优化问题更易处理。不过，某些扩展公式的存在性和可高效构造性之间存在差距。 本文聚焦于一种产生扩展公式的重要工具——通信协议。Yannakakis 证明了计算多面体 $P = \{x : Ax ≤ b\} ⊆ R^n$ 松弛矩阵的确定性通信协议可用于为 $P$ 产生扩展公式，其不等式数量最多为 $2^c$，其中 $c$ 是协议的复杂度。但这种方法虽具构造性，却不高效，会产生 $n + 2^c$ 个变量、$2^c$ 个不等式以及每行 $A$ 对应一个方程，且要去除冗余方程可能需遍历完整（可能是指数级大小）的列表。Yannakakis 技术的主要应用是处理完美图的稳定集多面体，然而我们仍不清楚完美图的稳定集多面体是否具有多项式大小的扩展复杂度。 #### 2. 预备知识 ##### 2.1 确定性通信协议 设 $M$ 是一个非负矩阵，行集为 $X$，列集为 $Y$，有两个代理 Alice 和 Bob。Alice 输入行索引 $i ∈ X$，Bob 输入列索引 $j ∈ Y$，他们通过预先指定的机制交换信息来确定 $M_{ij}$，这种机制就是确定性协议。该协议可建模为一棵有根树： - 每个顶点代表 Alice 或 Bob 发送一位的步骤，标记为 $A$ 或 $B$。 - 树是二叉树，每条边代表发送的 $0$ 或 $1$。 - 叶子节点表示协议终止，并标记相应的输出。 协议计算 $M$ 是指对于 Alice 的任何输入 $i$ 和 Bob 的任何输入 $j$，都能返回 $M_{ij}$。确定性协议可由以下参数确定： - 有根二叉树 $\tau$，节点集为 $V$。 - 函数 $\ell: V → \{A, B\}$，将每个顶点关联到其类型。 - 对于每个叶子节点 $v ∈ V$，有一个非负数 $\Lambda_v$ 对应在 $v$ 处输出的值。 - 对于每个 $v ∈ V$，有集合 $S_v$ 是 $X × Y$ 中的对 $(i, j)$，使得在输入 $(i, j)$ 时，协议中对应