PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

Sebastian Ben Daniel

arXiv:2609.31053v1cs.CC

TL;DR

Selectors and binary comparators reveal only partial membership information, raising the question of how much advice enables exact recognition. The paper gives binary comparators common fixed linear advice with short certificates, and establishes linear and quadratic advice orders for selectors in average-case and worst-case regimes.

  • Problem

    Selectors and binary membership comparators provide only partial membership information, motivating the question of how much nonuniform advice is needed for exact recognition.

    Source: §1 · p. 3

  • Method

    For binary comparability, the paper uses a deterministic polynomial-time verifier with common fixed advice and certificates to verify either membership bit.

    Source: §3 · p. 6

  • Results

    For every L in 2-mc, a deterministic polynomial-time verifier uses advice of length 3n + 5 and certificates of at most 5n + 12 bits to verify membership or nonmembership.

    Source: §3 · p. 6

  • Takeaways & Limitations

    One oracle-relative P-selective language realizes both selector advice orders and has linear coin-dependent advice with logarithmically many coins.

    Source: §1.1 · p. 3

    The comparator theorem is specific to binary comparability, and its advice coefficient and witness and call constants are not shown optimal.

    Source: §3.2 · p. 8

Abstract

from arXiv · show

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: $\Theta(n)$ for errorless average-case computation and $\Theta(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.

1 Introduction

The paper asks how ordinary advice can turn selector and comparator answers into exact recognition. It extends fixed linear nondeterministic advice to binary comparability and establishes linear and quadratic advice orders for two selector computation regimes, with lower-bound scope carefully limited.

1.1 Results and scope

  • Every binary membership-comparable language has common fixed advice of 3n + 5 bits for NP and coNP verification, with certificates of at most 5n + 12 bits.Verification makes at most six comparator calls on distinct equal-length inputs.Source: §1.1 · p. 3

1.2 Proof overview and context

  • The comparator proof replaces a tournament king with an independent two-step cover of true signed literals and a short-forcing-or-exact-majority dichotomy.The result relativizes; an advice-preserving isolation transfer gives 2-mc ⊆ P/O(n) under a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT.Source: §1.1 · p. 3, §1.2 · pp. 4–5

1.1 Results and scope

  • Selector advice is Θ(n) for errorless average-case computation and Θ(n^2) for worst-case bounded-error computation, independently of the interpreter’s finite coin bound in the latter regime.One oracle-relative P-selective language realizes both orders.Source: §1.1 · p. 3
  • The average- and worst-case lower bounds apply to tournament-query procedures and relativized languages, not unconditionally to unrelativized P-selective sets or 2-mc.For polynomial-time decoding, the comparison remains against Ko’s n^2 + n-bit upper bound; a smaller n^2/2 + O(n log n) bound uses unrestricted finite oracle-independent computation.Source: §1.1 · p. 3

1.2 Proof overview and context

  • Selector upper bounds use positive and negative anchors, two-step certificates, density bounds, and shifted small-bias samples to obtain linear advice in the studied regimes.For a bounded-time heuristic, one shift regenerates a sample and one Hamiltonian-path cut encodes its labels.Source: §1.1 · p. 3, §1.2 · p. 4
  • The paper distinguishes its fixed-advice binary theorem from earlier P-selective-set bounds and from advice depending on coins or witnesses.The introduction situates the results alongside Ko’s quadratic bound and the optimal nondeterministic (n + 1)-bit selector bound.Source: §1.2 · p. 5

2 Preliminaries: selectors, comparators, and advice

The preliminaries distinguish selectors from binary comparators and fix the meaning of ordinary advice and related computation models. For selector algorithms, weighted tournament anchors yield sound two-step certificates whose density profile controls average cost.

2 Preliminaries: selectors, comparators, and advice

  • Ordinary advice is fixed for each input length, independently of inputs, coins, or witnesses; exact polynomial mean time is an expectation under the uniform distribution.An errorless heuristic outputs the correct bit or abstains on every input and tape.Source: §2 · p. 5
  • A selector returns a member whenever either input is in the language, whereas a binary comparator excludes one of the four membership vectors without necessarily determining either bit.The binary theorem requires correctness only on distinct equal-length inputs.Source: §2 · p. 5

2.1 Tournament anchors for the selector upper bounds

  • In a weighted tournament, a minimum weighted-outdegree vertex yields the tail bound ν{x : p → x, ν(Ix) ≤ t} ≤ 2t.The two-step witness sets compare the mass of paths through x in each direction.Source: §2.1 · p. 6
  • A positive minimum-outdegree anchor and a negative minimum-indegree anchor give sound two-step certificates for unresolved inputs, with density ρ(x) at least ν(x) and lower-tail mass at most 4t.Intermediate vertices need no advised labels: their tournament edges certify the respective membership bits.Source: §2.1 · p. 6

3 Binary comparators: fixed linear advice and short certificates

Binary comparability admits common linear advice for nondeterministic recognition in both directions. The proof uses checked signed implications and an independent two-step cover, then either short forcing certificates or an exact majority prediction.

3 Binary comparators: fixed linear advice and short certificates

  • Every language in 2-mc has common advice of 3n + 5 bits for NP and coNP verification, with witnesses of at most 5n + 12 bits.Verification uses at most six comparator calls, only on distinct equal-length inputs.Source: §3 · p. 6

3.1 Signed implications and independent two-step covers

  • The proof converts each excluded membership vector into checked implications between signed literals, so every implication walk is a sound membership certificate.An independent outward two-step cover exists even when the true-literal graph has missing edges.Source: §3.1 · pp. 6–7
  • Among covering literals that are not short-forced, each true literal has at most one outgoing neighbor, yielding the proof’s forcing-versus-majority split.A literal is short-forced when its negation implies it within four steps.Source: §3.1 · p. 7

3.2 Short certificates or an exact three-row majority

  • When at most two covering literals remain, advice and short forcing paths support certificate verification; when at least three remain, their row predictions recover every bit by exact majority.The advice has three signed-literal slots and a two-bit mode header; witnesses use at most five (n + 1)-bit slots.Source: §3.2 · pp. 7–8
  • The theorem relativizes, and under deterministic polynomial-time promise Unique-Circuit-SAT the advice-preserving transfer gives 2-mc ⊆ P/O(n).Neither the advice coefficient nor the witness and call constants are proved optimal; the binary argument does not establish the corresponding higher-arity theorem.Source: §3.2 · p. 8

4 Selector upper bounds: linear advice on average

For P-selective languages, the section develops ordinary-advice upper bounds for exact mean-time and errorless computation. It combines anchor-based certificates with randomized sampling or a shifted sample encoded by one path cut.

4 Selector upper bounds: linear advice on average

  • 3n + O(1) ordinary advice gives every P-selective language an exact deterministic decider with polynomial uniform mean time.Its worst-case time is 2^n poly(n), and one advice sequence supports every fixed inverse-polynomial timeout guarantee.Source: §4 · p. 8
  • 2n + O(1) ordinary advice gives an errorless interpreter polynomial mean time on exactly polynomial-time samplable ensembles, terminating almost surely on every input.Truncation after M samples has average abstention at most 8/(M + 1), or 4/(M + 1) for direct uniform sampling.Source: §4 · pp. 8–9
  • Anchor certificate density controls expected sampling cost, while mixing the target distribution with the uniform distribution preserves eventual answers outside the target support.The selector upper bounds relativize and use only selector evaluations; the density argument is not extended here to all binary comparators.Source: §4 · pp. 8–9
  • For fixed positive c, deterministic polynomial-time errorless computation with uniform abstention at most n^-c uses n + (2c + 2) log n + O(1) advice bits.The refined bound is n + (c + 2) log n + log log n + O_c(1), with advice permitted to depend on c.Source: §4 · p. 9
  • The errorless heuristic uses a shifted sample whose labels are encoded by one cut in a directed Hamiltonian path, then regenerates the sample to test sound certificates.The sample labels form a positive prefix followed by a negative suffix; the construction uses only consecutive path edges.Source: §4 · p. 9

5 Black-box lower bounds

The section establishes advice lower bounds for black-box tournament-query procedures using transcript freezing and a hidden-core distribution. It also separates unrestricted query-model advice from polynomial-time decoding guarantees.

5.1 The model

  • The model gives an interpreter only tournament-edge queries, with each input a fresh run; one edge query simulates one query to the selector-induced mixed-vector comparator.A legal instance is a tournament on {0, 1}^n and a set P beating its complement; sound advice never gives a wrong bit.Source: §5.1 · pp. 9–10

5.2 Transcript freezing for errorless heuristics

  • Transcript freezing forces n − O_q(log n) advice for polynomial-query errorless heuristics, even at coverage 1/2, and truncation transfers the linear order to exact polynomial mean time.The argument preserves selected erroneous transcripts while fixing at most 2q + 1 vertices per eliminated advice string.Source: §5.2 · pp. 10–11

5.3 The hidden-core distribution and its deterministic bound

  • A procedure-independent hidden-core distribution yields a finite lower bound that, after a union bound over advice, gives a leading coefficient of 1/4 for quadratic advice.The distribution and estimate are uniform over fixed procedures, advice, and tapes, enabling the randomized transfer.Source: §5.3 · pp. 11–12

5.4 Randomized lifting with no dependence on coin length

  • For polynomial q, ordinary advice requires n^2/4 - O_q(n log n) bits for worst-case bounded-error decoding, independently of the interpreter’s finite coin bound.For q ≤ 2εn, the lower bound is (1 − ε)^2n^2/4 − O(n log n).Source: §5.4 · p. 12

5.5 The leading constant: queries versus polynomial time

  • With unrestricted finite oracle-independent computation, a deterministic decoder uses n + 2 comparisons and n^2/2 + O(n log n) advice bits; this does not improve Ko’s polynomial-time coefficient.The universal-family reconstruction is not shown to be polynomial-time, and the single-core typical-instance bound does not cover rare instances.Source: §5.5 · p. 13

6 One oracle realizing both tight orders

A single oracle-relative P-selective language realizes linear exact mean-time advice and quadratic worst-case bounded-error advice, while ordinary advice remains weaker than coin-dependent advice. The section also shows that the lower bounds are relativized and that a global selector must handle inputs from different active lengths.

6 One oracle realizing both tight orders

  • Θ(n) advice for exact polynomial uniform mean time and Θ(n^2) for worst-case bounded-error polynomial time are both realized on one oracle-relative P-selective language.The bounded-error lower bound holds even with polynomially many coins.Source: §6 · pp. 13–14
  • The construction interleaves worst-case and heuristic requirements at active lengths, with a global selector using membership records to handle pairs from different lengths.The lower bounds are forced at active lengths, not at every length.Source: §6 · p. 14

6.1 Opposing relativizations and the two advice models

  • For every oracle, binary comparators have linear nondeterministic advice, but neither deterministic nor bounded-error O(n) advice containment follows by a proof valid relative to every oracle.The passage states that an unrelativized counterexample would refute U and imply P ≠ NP.Source: §6.1 · p. 14
  • A minimax distribution and a list of O(n) anchor-pair tuples yield an errorless coin-dependent interpreter with logarithmically many coins.The interpreter receives only the selected tuple, not the entire list.Source: §6.1 · p. 14
  • The same language has an errorless coin-dependent O(n)-advice interpreter using log n + O(1) coins, unlike its ordinary-advice bounded-error requirement.Its conclusive probability is at least 2/3 on every input.Source: §6 · p. 13, §6.1 · p. 14

7 What non-black-box access to the comparison program buys

Under promise Unique-Circuit-SAT, the paper transfers nondeterministic advice into deterministic advice by isolating witnesses in circuits compiled from the verifier. Applied to the binary-comparator verifier, this gives a conditional deterministic linear-advice consequence.

7 What non-black-box access to the comparison program buys

  • U is promise Unique-Circuit-SAT, not the total exact-one language or P = UP; the paper does not claim these hypotheses are strictly separated.The passage says U follows from P = NP and implies NP = RP by isolation.Source: §7 · pp. 14–15
  • Under U, a language with an existential verifier using advice a(n) and witnesses of length w(n) is in P/O(a(n) + w(n) + n).U is a deterministic polynomial-time promise solver that rejects unsatisfiable circuits and accepts circuits with exactly one solution; behavior on multiple solutions is unrestricted.Source: §7 · pp. 14–15
  • The transfer compiles the verifier into a circuit and tests hash restrictions at all prefixes, avoiding a factor-m loss while preserving rejection of unsatisfiable circuits.An expander walk visits good seeds for every positive input using a length-O(n) description.Source: §7 · p. 15
  • Substituting the comparator verifier's 3n + 5 advice bits and 5n + 12 witness bits gives 2-mc ⊆ P/O(n) under U.The transfer compiles the actual comparison program; comparison-oracle answers alone do not provide that circuit.Source: §7 · p. 15

8 Open problems

The open problems concern stronger lower-bound constants, efficient decoding, and weakening the promise-isolation assumption. The appendix's tournament setup and weighted lemma supply structural bounds on two-step witnesses.

8 Open problems

  • The paper leaves open whether query-model lower-bound constants can improve, whether efficient indexing beats coefficient 1, and whether constants for binary advice and certificates can be reduced.Higher-arity comparators require more than the one-premise implication used in the short-forcing proof.Source: §8 · p. 15
  • Neither P-sel ⊆ P/O(n) nor the analogous unconditional containment for 2-mc is established, and the paper asks whether weaker assumptions can replace U.The transfer uses the promise solver only on hash restrictions of circuits compiled from comparison verifiers.Source: §8 · p. 15

A.1 Conventions

  • Within a fixed-length slice, selector outcomes orient pairs as a tournament, with every positive vertex beating every negative vertex.The slice is partitioned into positive and negative strings.Source: §A.1 · p. 17

A.2 A weighted tournament lemma

  • In a weighted tournament, the appendix studies a minimum-outdegree pivot and the weight of vertices with small two-step witness sets; in the unweighted form, every vertex beaten by the pivot has a two-step path back.For vertices with at most k such witnesses, the unweighted bound is at most 2k − 1.Source: §A.2 · pp. 17–18
  • The unweighted lemma bounds the number of pivot-beaten vertices with at most k two-step witnesses by 2k − 1.The appendix also states that every vertex beaten by the pivot has a two-step path to it.Source: §A.2 · p. 18

A.3 Two advised vertices

Two nonuniformly chosen anchors give sound direct tests and two-step certificates for membership, with density bounds controlling the unresolved inputs. The proof uses only the anchors as advice, and the appendix notes that its selector arguments relativize.

A.3 Two advised vertices

  • The advice stores two anchors and a constant-size flag, totaling 2n + O(1) bits; the interpreter does not need labels for intermediate vertices.Edges involving the anchors supply the label information needed for soundness.Source: §A.3 · pp. 18–19
  • Direct tests and two-step certificates are sound, and every unresolved input has a certificate density profile bounded by the two-anchor proposition.An intermediate vertex in C+(x) certifies positivity, while one in C−(x) certifies negativity; each proposed certificate takes a constant number of selector evaluations to test.Source: §A.3 · pp. 18–19
  • Positive and negative certificate types cannot conflict because each two-step path forces the input to share the intermediate vertex's membership label.For unresolved positive inputs, the positive certificate set coincides with the relevant two-step witness set in the positive subtournament.Source: §A.3 · p. 19

B Full proofs of the average-case upper bounds

  • The selector arguments apply relative to arbitrary oracles, while their time qualifications distinguish exact mean-time computation from worst-case polynomial-time errorless heuristics.The appendix states a worst-case time of 2n poly(n) for the construction discussed there.Source: B Full proofs of the average-case… · p. 19

B.1 Main upper bounds

This section studies advice-based deciders for P-selective languages, developing exact and errorless upper bounds and ordinary-advice tradeoffs for deterministic and randomized procedures, alongside query–advice lower-bound constructions. It bounds black-box deciders by showing that ambiguous runs leave fresh choices and that quadratic advice is necessary across polynomial and sublinear query regimes.

B.2 Exact randomized search

  • 2n + O(1) ordinary advice gives an almost-surely terminating, never-incorrect randomized interpreter for efficiently samplable distributions, with O(n) mean sampled certificates.Truncating after M samples gives average abstention at most 8/(M + 1), or 4/(M + 1) under the direct uniform construction; the expectation is over inputs and random choices, not a per-input polynomial bound.Source: §B.1 · pp. 19–20, The certificate-search procedure · p. 21

B.1 Main upper bounds

  • n + (c + 2) log n + log log n + O_c(1) advice achieves uniform abstention at most n^-c for each fixed positive integer c.The refinement's advice may depend on c, unlike the 3n + O(1) sequence, which supports every fixed inverse-polynomial timeout guarantee.Source: §B.1 · p. 20

B.4 Exact deterministic search with three linear-size fields

  • Successive translated small-bias candidate sets followed by exhaustive search yield an exact deterministic procedure, with one fixed shift chosen to bound its mean cost.The same shift is used across stages, and the stored fields p, q, the shift, and empty-class flags total 3n + O(1) bits.Source: §B.4 · p. 22

B.1 Main upper bounds

  • 3n + O(1) advice supports an exact deterministic decider with mean stage cost O(n^4) and worst-case time 2^n poly(n).A single advice sequence also supports every fixed inverse-polynomial timeout guarantee; truncation yields uniform abstention at most n^-c.Source: §B.1 · p. 19, §B.4 · pp. 22–23

B.5 One-step witnesses; B.6 Encoding all sample labels by one cut

  • A correctly labeled one-step witness certifies an input using one selector evaluation, and a Hamiltonian-path cut encodes M sample labels in at most ⌈log(M + 1)⌉ advice bits.The path's adjacent orientations ensure the sample labels form a prefix of ones followed by a suffix of zeros.Source: §B.5 · p. 23, §B.6 · pp. 23–24

B.7 Short-advice heuristics from one translate

  • For an efficiently samplable distribution, average abstention at most ε is achievable with advice r + ⌈log(M + 1)⌉, where M = O(r^2/ε^2), and every conclusive answer is correct.The method encodes the sample labels using one cut position and a shift; correctness also holds outside the distribution's support.Source: §B.7 · p. 24

C Hidden-core estimates and parameter optimization

  • The finite query–advice tradeoff theorem gives a random instance on which each deterministic black-box decider with query bound q is decided correctly by no advice string of length at most ℓ with probability strictly greater than 1/2.The theorem states parameter conditions on q, k, ℓ, and m; the supplied passage does not include the full tradeoff expression.Source: C Hidden-core estimates and parameter… · p. 25

C.1 The distribution; C.2 Ambiguous runs

  • The lower-bound construction hides independently labeled core points among buckets, and analyzes ambiguous runs whose transcripts can conceal the input point's label.Each bucket has a random tail and label, and each pair of distinct buckets has an orientation coin; core points beat points outside the core, and opposite labels determine the winner between core points.Source: §C.1 · p. 25, §C.2 · p. 25

C.2 Ambiguous runs

  • In Theorem C.1’s setup, the union bound makes the probability that any eligible advice string decides the entire instance strictly less than 1/2.The bound uses the fresh choices left by runs with fewer than k discoveries: each round survives with conditional probability at most 1 − 2^-k.Source: §C.2 · p. 26

C.3 Quadratic asymptotics and the query tradeoff

  • For polynomially many queries, every deterministic q-query black-box decider has a legal instance requiring n^2/4 − O_q(n log n) advice bits; for q ≤ 2εn, the bound is (1 − ε)2n^2/4 − O(n log n).The stated corollary applies when 1 ≤ q ≤ 2n − 4.Source: §C.3 · p. 27

C.4 Finite randomized tradeoff and its optimization

The section derives finite randomized query–advice lower bounds from a hidden-core distribution and optimizes them to show quadratic ordinary advice is necessary, regardless of coin bound. It also distinguishes the query-only comparison from polynomial-time bounds and notes an inverse-polynomial-advantage extension.

C.4 Finite randomized tradeoff and its optimization

  • The hidden-core bound applies to randomized deciders by transferring a fixed-procedure correctness bound and union-bounding over advice strings.The probability bound concerns correctness on all inputs, and the underlying ∆ is independent of the fixed procedure, advice, and hardwired random tape.Source: §C.4 · pp. 27–28
  • n^2/4 − O_q(n log n) bits are necessary for polynomial q, and the bound is independent of the interpreter’s finite coin bound.The finite tradeoff yields the polynomial-query asymptotic; the randomized theorem counts advice strings, not random tapes.Source: §C.4 · pp. 27–28
  • Inverse-polynomial pointwise advantage preserves the leading quadratic lower bound, with an O(n log n) loss for polynomial q.This extension concerns a specified uniform advantage on every input, not arbitrary unbounded-error acceptance probabilities.Source: §C.4 · p. 28

D The query-only constant and the single-core family

  • The query-only comparison is n^2/4 − O(n log n) versus n^2/2 + O(n log n), but the smaller upper coefficient is not established for polynomial-time decoding.The half-quadratic upper bound is limited to unrestricted finite internal computation; efficient indexing is not shown.Source: D The query-only constant and the… · p. 29, §D.1 · p. 29

D.1 Ko’s polynomial-time upper bound

  • Ko’s black-box implementation uses n^2 + n advice bits and at most n queries.It stores selected positive anchors in n fields and a presence mask, then accepts inputs equal to or beating a present anchor.Source: §D.1 · p. 29

D.2 A half-quadratic universal family in the query model

The section gives a query-only deterministic upper bound using a universal family of short valid tuples, then contrasts it with a typical-instance bound for a single-core distribution. The universal-family construction permits unrestricted finite computation, while the typical-instance result does not rule out stronger lower bounds on rare instances.

D.2 A half-quadratic universal family in the query model

  • A valid tuple consists of positive anchors such that every positive input is an entry or beats an entry; checking equality or beating an entry rejects every negative input.The empty tuple is valid exactly when there are no positive inputs.Source: §D.2 · p. 29
  • Uniform sampling of tuples gives a covering family, whose lexicographically first instance-dependent-free index can be computed by exhaustive finite search.The resulting decoder uses the advised index to reconstruct a tuple and test the input against its entries; the indexing computation is not shown polynomial-time.Source: §D.2 · pp. 29–31
  • The query-only comparison is n^2/4 − O(n log n) against n^2/2 + O(n log n), with the upper bound using at most n + 2 comparisons.The lower bound allows bounded-error randomness; the upper bound is deterministic.Source: §D.2 · pp. 30–31

D.3 The single-core family on typical instances

  • For even n and m = n/2, the typical-instance advice bound is n^2/4 + O_d(n), with success probability at least 1 − 2^-d − exp(−Ω(m)).The construction stores a label mask and tails of positively labeled buckets to obtain anchors.Source: §D.3 · p. 31
  • The typical-instance upper bound does not exclude stronger lower bounds on rare members, and nested-core advice costs cannot simply be added.Inner anchors can already certify outer layers; no lower coefficient above 1/4 is established here.Source: §D.3 · p. 31

E.1 The joint sparse-length construction

The construction builds a single relativized P-selective language that separates ordinary-advice requirements for worst-case decision and errorless heuristics. The diagonalization acts at sparse active lengths, while the language retains selector upper bounds for average-case computation.

E.1 The joint sparse-length construction

  • Every polynomial-time randomized decider or errorless heuristic is enumerated with a clock and revisited at arbitrarily large stages, allowing failures to be fixed permanently at selected lengths.At each active length, the current machine sees only same-length tournament edges depending on the instance; earlier oracle answers are fixed and later records are inaccessible.Source: §E.1 · pp. 32–34
  • For worst-case decision, the construction chooses a tournament instance on which every advice string within the budget fails on some input, including randomized machines directly.The diagonalization applies the finite lower bound to the probabilistic machine rather than enumerating its random tapes.Source: §E.1 · p. 33
  • For errorless heuristics, each sound advice string has uniform coverage strictly below 1/2 on a selected active length.Thus no designated advice sequence within the budget achieves soundness and coverage of at least 1/2 at every length.Source: §E.1 · pp. 32–33
  • The oracle records define a global polynomial-time selector by answering same-length comparisons from tournament edges and using membership records for unequal active lengths.The selector returns a positive shorter input when available, and otherwise returns the longer input.Source: §E.1 · p. 34
  • The oracle language has O(n) ordinary advice for deterministic exact mean-time computation and polynomial-time errorless heuristics, but Θ(n^2) for worst-case bounded-error polynomial time.The lower bounds follow from separate diagonal requirements; the upper bounds relativize from selector results.Source: §E.1 · pp. 32, 34
  • The lower-bound scope is sparse: hard failures occur at active lengths, while the language is empty at inactive lengths.The bounds distinguish exact mean-time computation from worst-case polynomial time and concern an oracle construction, not unconditional hardness for unrelativized P-selective sets.Source: §E.1 · p. 34

E.2 Nondeterministic advice and opposing relativizations

The appendices establish relativized nondeterministic advice bounds and contrast ordinary advice with advice chosen after random coins. A single oracle-relative P-selective language separates linear average-case advice from quadratic worst-case ordinary advice, even when polynomially many coins are allowed.

E.2 Nondeterministic advice and opposing relativizations

  • For every oracle, P-selective languages have linear nondeterministic advice with linear-length witnesses, using positive and negative tournament anchors for NP and coNP verification.The proof uses the tournament argument of and witness accounting of.Source: §E.2 · p. 34
  • Relativizing arguments cannot settle the stated containment questions: one oracle falsifies the containments, while a PSPACE-complete oracle supports the corresponding inclusions.The consequences include that an unrelativized counterexample would refute hypothesis U, and a BPP counterexample would also imply NP ⊄ BPP.Source: §E.2 · p. 35

E.3 Ordinary advice versus advice chosen after the coins

  • For every oracle, P-selective languages have an errorless interpreter using O(n) coin-dependent advice and log n + O(1) coins.Advice may vary with the random tape; the construction selects among a list of anchor-pair triples while preserving soundness and conclusive probability at least 2/3 on every input.Source: §E.3 · pp. 35–36
  • One oracle-relative P-selective language needs quadratic ordinary advice for bounded-error polynomial-time decision despite the O(n) coin-dependent upper bound.The ordinary-advice lower bound holds for any polynomial coin bound, whereas the coin-dependent interpreter uses log n + O(1) coins.Source: §E.3 · pp. 35–36
  • The transfer argument’s query cost is O(nq), independent of the coin bound, because it averages over tapes rather than enumerating them.With coin-dependent advice, repeated advice strings may vary across tapes and cannot be absorbed into one fixed advice string.Source: §E.3 · p. 36

F Full proofs for the conditional containment

The conditional containment uses a deterministic promise-unique circuit solver together with an advice-preserving isolation transfer. The proof converts linear-witness verifiers into deterministic linear-advice deciders, while appendices specify the transfer, advice constructions, and limits of the claims.

F Full proofs for the conditional containment

  • If promise Unique-Circuit-SAT has a deterministic polynomial-time algorithm, then binary membership-comparable languages have deterministic O(n) advice.The hypothesis distinguishes zero from one satisfying assignment and must halt on all circuits, while either answer is allowed on circuits with multiple satisfying assignments.Source: F Full proofs for the conditional… · pp. 36–37

F.1 A general linear-witness transfer

  • The advice-preserving transfer turns an advice-and-witness verifier into a deterministic decider using advice length a(n) + O(w(n) + n).It compiles each input’s verifier into a circuit with exactly w(n) free witness bits and uses a short expander walk to hit the relevant sets.Source: §F.1 · pp. 37–38
  • The proof uses a linear-length seed for pairwise-independent hashing, tests all hash prefixes, and amplifies with one expander walk.These choices preserve the advice-length parameter rather than using an unrestricted randomized SAT simulation.Source: §F.1 · pp. 37–38
  • Linear-seed isolation gives a one-sided procedure using 3m + 1 seed bits that rejects unsatisfiable circuits always and accepts satisfiable circuits with probability at least 3/16.Testing every hash prefix avoids losing a factor m in the isolation probability.Source: §F.1 · pp. 37–38

F.2 Applying the transfer to P-selective sets

  • Applying the transfer to P-selective sets yields deterministic linear advice, and under the same hypothesis 2-mc ⊆ P/O(n).The comparator application compiles its polynomial-time program; it is not a black-box simulation, and the implication does not automatically relativize.Source: F Full proofs for the conditional… · p. 36, §F.2 · p. 39

G.2 Refining the logarithmic overhead

H.1 Advice and certificate layouts

  • The binary-comparator verifier uses advice of exactly 3n + 5 bits and certificate-mode witnesses of 5n + 12 bits, with at most six comparator evaluations.Correctness is required for the designated advice sequence; the theorem does not make every input–advice pair an NP ∩ coNP language.Source: §H.1 · p. 41

H.3 A disjunction example and the binary restriction

  • The binary proof establishes neither a higher-arity fixed-linear-advice theorem nor a general extension of selector-specific errorless mean-time bounds.For arity k, forcing one literal may require k − 1 premises, so binary nonadjacency does not directly provide the needed single edge.Source: §H.3 · p. 42
Loading 2609.31053v1…