一句话:证明 FPC 无法以任何常数因子近似 Unique Games 的最优值,并给出新的不可近似间隙。
本文研究在带计数的不动点逻辑(FPC)中能否近似 Unique Games 实例的最优值。作者形式化地证明:任何用 FPC 可解释的映射若把关系结构编码的 Unique Games 实例映到有理数并试图逼近可满足约束比例,其精度存在下界。主要结果有两个 FPC 不可表达性结论:存在 (1/2, 1/3+δ) 不可近似间隙,且无法在任意常数因子内近似。方法上,构造不同于通常基于 CFI 的论证:从很大围长的图出发,用 F2 上的随机仿射向量空间给边标号以确定两个结构中的约束;Duplicator 策略维护覆盖被 pebble 顶点的最小树上的部分同构。工作以形式证明完成评估。
We study the extent to which it is possible to approximate the optimal value of a Unique Games instance in Fixed-Point Logic with Counting (FPC). Formally, we prove lower bounds against the accuracy of FPC-interpretations that map Unique Games instances (encoded as relational structures) to rational numbers giving the approximate fraction of constraints that can be satisfied. We prove two new FPC-inexpressibility results for Unique Games: the existence of a $(1/2, 1/3 + \delta)$-inapproximability gap, and inapproximability to within any constant factor. Previous recent work has established similar FPC-inapproximability results for a small handful of other problems. Our construction builds upon some of these ideas, but contains a novel technique. While most FPC-inexpressibility results are based on variants of the CFI-construction, ours is significantly different. We start with a graph of very large girth and label the edges with random affine vector spaces over $\mathbb{F}_2$ that determine the constraints in the two structures. Duplicator's strategy involves maintaining a partial isomorphism over a minimal tree that spans the pebbled vertices of the graph.