P-selective language recognition needs quarter n squared advice bits

A Sharp Quadratic Bound for the Advice Complexity of Selectors

Computational Complexity

Summary

P-selective languages are special sets of strings where a fast algorithm can choose a string that belongs to the language from any pair. The authors found the exact amount of extra information (called advice) needed for a polynomial-time algorithm to recognize these languages. They proved that about one quarter times n squared bits of advice are necessary and sufficient, improving on the previous known bound. This result also sets limits on how much this requirement can be lowered by certain complexity assumptions or query types.

What this means in practice

  • For algorithm designers: Determine precise limits on extra information needed to design polynomial-time algorithms recognizing p-selective languages.
  • For complexity theorists: Use refined bounds to rule out simpler decoder models or advice reductions when analyzing complexity classes related to p-selective languages.

A theory result. No direct application yet.

Authors

Sebastian Ben Daniel

Abstract

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 $n^2+n$ bits, and for polynomial-time recognition the leading constant has stood since. We show that the right constant is $1/4$. In the selector-query model the answer is unconditional. A single computable decoder recognizes every legal cut on $n$-bit strings with $n^2/4+O(n)$ advice bits and $n$ nonadaptive comparisons. Conversely, every randomized decoder making polynomially many queries needs $n^2/4-O(n\log n)$ bits at error $1/3$, even when its queries are adaptive evaluations of individual-degree-two extensions of the selector table. The degree matters: with multilinear extensions, $n+1$ bits suffice and are optimal. Under the hypothesis that $\mathrm E$ requires exponential-size circuits with SAT gates, every P-selective language has a polynomial-time decoder with $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 $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 $2^v$ vertices, the cost is $u(n-u)\pm O(n\log n)$ with $u=\min\{v,n/2\}$. When $\log n\ll v=o(n)$ this is $(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 $2^{r^2-O(r)}$ different $r$-tuples cover any side, for a suitable $r$.