paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Indivisibility and uniform computational strength

不可分性与一致计算强度
LMCS vol.Volume 21, Issue 22025匹配度 0/10 · 论文属于可计算性理论与 Weihrauch 复杂度研究,讨论有理数序和等价关系的不可分问题,与用户画像中的 PL/AI、静态分析、Agent、浮点程序分析及贝叶斯程序分析均无直接关联。引用 2 inbox
Kenneth Gill
crossref: 2026-09-10

AI 速览

一句话:用 Weihrauch 复杂度刻画有理数序与等价关系 ℰ 的不可分问题,并定位其计算强度。

论文研究可数结构的不可分性问题:给定有限着色,需输出一个单色同构子拷贝。作者考察两个结构——作为线序的有理数 Q,以及具有可数多个等价类、每个类可数成员的等价关系 ℰ——的不可分问题的 Weihrauch 复杂度。通过与其他基准问题的 Weihrauch 度分离,证明 Q 的不可分问题不能解决“给定存在单色有理区间的着色时找出该区间”的问题;并证明 ℰ 的不可分问题的 Weihrauch 度严格介于 RT² 与 SRT² 之间,而这两个 Ramsey 定理变体的反数学分离此前仍开放。

问题
研究可数结构的不可分问题在 Weihrauch 复杂度意义下的计算强度,特别是有理数线序 Q 和等价关系 ℰ 的不可分问题与已知基准问题的关系。
方法
将每个不可分结构对应为从呈现和有限着色输出单色同构子拷贝的不可分问题,使用 Weihrauch 度与分离技术比较其计算强度。
评估
通过 Weihrauch 度分离证明:Q 的不可分问题不能求单色有理区间;ℰ 的不可分度严格位于 RT² 和 SRT² 之间。
原文摘要(Abstract)

A countable structure is indivisible if for every coloring with finite range there is a monochromatic isomorphic subcopy of the structure. Each indivisible structure naturally corresponds to an indivisibility problem which outputs such a subcopy given a presentation and coloring. We investigate the Weihrauch complexity of the indivisibility problems for two structures: the rational numbers $\mathbb{Q}$ as a linear order, and the equivalence relation $\mathscr{E}$ with countably many equivalence classes each having countably many members. We separate the Weihrauch degrees of both corresponding indivisibility problems from several benchmarks, showing in particular that the indivisibility problem for $\mathbb{Q}$ cannot solve the problem of finding a monochromatic rational interval given a coloring for which there is one; and that the Weihrauch degree of the indivisibility problem for $\mathscr{E}$ is strictly between those of $\mathsf{RT}^2$ and $\mathsf{SRT}^2$, two widely studied variants of Ramsey's theorem for pairs whose reverse-mathematical separation was open until recently.

链接与引用

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

BibTeX
@article{abs-2312-03919,
  title = {Indivisibility and uniform computational strength},
  author = {Kenneth Gill},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 21, Issue 2},
  year = {2025},
  doi = {10.46298/lmcs-21(2:22)2025}
}