跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24913 · v1

A Sharp Quadratic Bound for the Advice Complexity of Selectors

选择器建议复杂度的尖锐二次界

首次提交 2026-11-19 02:47
版本更新 2026-11-19 02:47
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

A language is P-selective if a polynomial-time algorithm, given two strings, picks one that belongs to the language whenever either does. Ko showed in 1983 that every P-selective language is recognized in polynomial time with quadratic advice; his argument uses n2+nn^2+n bits, and for polynomial-time recognition the leading constant has stood since. We show that the right constant is 1/41/4. In the selector-query model the answer is unconditional. A single computable decoder recognizes every legal cut on nn-bit strings with n2/4+O(n)n^2/4+O(n) advice bits and nn nonadaptive comparisons. Conversely, every randomized decoder making polynomially many queries needs n2/4−O(nlog⁡n)n^2/4-O(n\log n) bits at error 1/31/3, even when its queries are adaptive evaluations of individual-degree-two extensions of the selector table. The degree matters: with multilinear extensions, n+1n+1 bits suffice and are optimal. Under the hypothesis that E\mathrm E requires exponential-size circuits with SAT gates, every P-selective language has a polynomial-time decoder with n2/4+O(n)n^2/4+O(n) advice bits. From this hypothesis no relativizing argument, and no argument that algebrizes with degree-two extensions, can lower the constant: one oracle satisfies the hypothesis and carries a selective language that needs n2/4−o(n2)n^2/4-o(n^2) bits against randomized decoders with degree-two access. The cost is set by the two strong components of the selector tournament adjacent to the cut. If the smaller has 2v2^v vertices, the cost is u(n−u)±O(nlog⁡n)u(n-u)\pm O(n\log n) with u=min⁡{v,n/2}u=\min\{v,n/2\}. When log⁡n≪v=o(n)\log n\ll v=o(n) this is (1+o(1))nv(1+o(1))nv, attained in polynomial time with no hypothesis. The upper bounds rest on a fixed-point distribution on the vertices of a tournament. Its power moment shows that 2r2−O(r)2^{r^2-O(r)} different rr-tuples cover any side, for a suitable rr.

AI 论文解读

基于摘要 · 非全文审阅

作者证明P-选择语言在建议复杂度中的二次项常数从1改进到1/4,并在选择器查询模型下给出无条件匹配下界。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 02:47 · 最新观测版本

A Sharp Quadratic Bound for the Advice Complexity of Selectors

A language is P-selective if a polynomial-time algorithm, given two strings, picks one that belongs to the language whenever either does. Ko showed in 1983 that every P-selective language is recognized in polynomial time with quadratic advice; his argument uses n2+nn^2+n bits, and for polynomial-time recognition the leading constant has stood since. We show that the right constant is 1/41/4. In the selector-query model the answer is unconditional. A single computable decoder recognizes every legal cut on nn-bit strings with n2/4+O(n)n^2/4+O(n) advice bits and nn nonadaptive comparisons. Conversely, every randomized decoder making polynomially many queries needs n2/4−O(nlog⁡n)n^2/4-O(n\log n) bits at error 1/31/3, even when its queries are adaptive evaluations of individual-degree-two extensions of the selector table. The degree matters: with multilinear extensions, n+1n+1 bits suffice and are optimal. Under the hypothesis that E\mathrm E requires exponential-size circuits with SAT gates, every P-selective language has a polynomial-time decoder with n2/4+O(n)n^2/4+O(n) advice bits. From this hypothesis no relativizing argument, and no argument that algebrizes with degree-two extensions, can lower the constant: one oracle satisfies the hypothesis and carries a selective language that needs n2/4−o(n2)n^2/4-o(n^2) bits against randomized decoders with degree-two access. The cost is set by the two strong components of the selector tournament adjacent to the cut. If the smaller has 2v2^v vertices, the cost is u(n−u)±O(nlog⁡n)u(n-u)\pm O(n\log n) with u=min⁡{v,n/2}u=\min\{v,n/2\}. When log⁡n≪v=o(n)\log n\ll v=o(n) this is (1+o(1))nv(1+o(1))nv, attained in polynomial time with no hypothesis. The upper bounds rest on a fixed-point distribution on the vertices of a tournament. Its power moment shows that 2r2−O(r)2^{r^2-O(r)} different rr-tuples cover any side, for a suitable rr.

查看此版本解读 →查看此版本原文 ↗