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