← 研踪 PaperTrailarXiv: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
摘要
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 bits, and for polynomial-time recognition the leading constant has stood since. We show that the right constant is . In the selector-query model the answer is unconditional. A single computable decoder recognizes every legal cut on -bit strings with advice bits and nonadaptive comparisons. Conversely, every randomized decoder making polynomially many queries needs bits at error , even when its queries are adaptive evaluations of individual-degree-two extensions of the selector table. The degree matters: with multilinear extensions, bits suffice and are optimal. Under the hypothesis that requires exponential-size circuits with SAT gates, every P-selective language has a polynomial-time decoder with 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 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 vertices, the cost is with . When this is , 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 different -tuples cover any side, for a suitable .
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 bits, and for polynomial-time recognition the leading constant has stood since. We show that the right constant is . In the selector-query model the answer is unconditional. A single computable decoder recognizes every legal cut on -bit strings with advice bits and nonadaptive comparisons. Conversely, every randomized decoder making polynomially many queries needs bits at error , even when its queries are adaptive evaluations of individual-degree-two extensions of the selector table. The degree matters: with multilinear extensions, bits suffice and are optimal. Under the hypothesis that requires exponential-size circuits with SAT gates, every P-selective language has a polynomial-time decoder with 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 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 vertices, the cost is with . When this is , 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 different -tuples cover any side, for a suitable .
查看此版本解读 →查看此版本原文 ↗