paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Inapproximability of Unique Games in Fixed-Point Logic with Counting

带计数的不动点逻辑中 Unique Games 的不可近似性
LMCS vol.Volume 20, Issue 22024匹配度 1/10 · 该论文属于有限模型论与描述复杂性,研究 FPC 对 Unique Games 的不可近似性,不涉及程序分析、静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户研究画像的核心方向几乎无交集。引用 0 inbox
Jamie Tucker-Foltz
crossref: 2026-09-10

AI 速览

一句话:证明 FPC 无法以任何常数因子近似 Unique Games 的最优值,并给出新的不可近似间隙。

本文研究在带计数的不动点逻辑(FPC)中能否近似 Unique Games 实例的最优值。作者形式化地证明:任何用 FPC 可解释的映射若把关系结构编码的 Unique Games 实例映到有理数并试图逼近可满足约束比例,其精度存在下界。主要结果有两个 FPC 不可表达性结论:存在 (1/2, 1/3+δ) 不可近似间隙,且无法在任意常数因子内近似。方法上,构造不同于通常基于 CFI 的论证:从很大围长的图出发,用 F2 上的随机仿射向量空间给边标号以确定两个结构中的约束;Duplicator 策略维护覆盖被 pebble 顶点的最小树上的部分同构。工作以形式证明完成评估。

问题
在带计数的不动点逻辑(FPC)中,近似 Unique Games 最优值的精度极限是什么,是否可能存在常数因子近似?
方法
构造两个难以区分的 Unique Games 结构:从大围长图出发,用 F2 上的随机仿射向量空间标号边以确定约束,并用 Duplicator 的部分同构策略证明 FPC 不可表达。
评估
以形式化不可表达性下界证明进行评估,得到 (1/2, 1/3+δ) 不可近似间隙以及任意常数因子不可近似两个结果。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2765,
  title = {Inapproximability of Unique Games in Fixed-Point Logic with Counting},
  author = {Jamie Tucker-Foltz},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 20, Issue 2},
  year = {2024},
  doi = {10.46298/lmcs-20(2:3)2024}
}