Boundaries for advice and information in membership decision problems
Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors
Computational Complexity
Summary
Deciding if a certain item belongs to a group can be tricky when only limited information is available. The authors study how extra hints, called advice, help turn partial information into exact decisions. They find new limits on the amount and types of advice needed for these decisions in complex cases, extending previous knowledge. Their work also explores how these limits change with different kinds of algorithms and randomness. This helps us understand what information is fundamentally needed to solve certain computational problems.
What this means in practice
- •For complexity theorists: Clarify limits on advice needed for solving membership problems, guiding design of algorithms with partial information.
- •For algorithm designers: Inform algorithm construction on feasibility and resource bounds when incorporating partial membership information and advice.
A theory result. No direct application yet.
Authors
Sebastian Ben Daniel
Abstract
Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership comparator merely excludes one of the four membership vectors of a pair. We ask how much nonuniform advice turns such information into exact recognition. Our main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language: $2-mc \subseteq NP /(3n+5)\cap\mathrm{coNP}/(3n+5)$, with common fixed advice and certificates of at most $5n+12$ bits. The class is strictly larger; some 2-mc sets are not truth-table reducible to any P-selective set. The proof replaces the tournament king by an independent two-step cover of true signed literals, together with a short-forcing-or-exact-majority dichotomy, and it relativizes. Via an advice-preserving isolation transfer, a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives $2-mc \subseteq P/O(n)$. For selectors we determine tight orders of ordinary advice: $Θ(n)$ for errorless average-case computation and $Θ(n^2)$ for worst-case bounded-error computation, the latter independent of the interpreter's coin bound. One oracle realizes both orders on a single language and separates ordinary from coin-dependent advice. The quadratic and linear lower bounds hold for tournament-query procedures and relativized languages, not unconditionally for unrelativized P-selective sets.