Source-linked AI summary

Consequences of Polylogarithmic Membership Comparability for SAT

Sebastian Ben Daniel

arXiv:2609.34952v1cs.CC

TL;DR

The paper asks what deterministic or randomized membership comparators that outperform uniform guessing imply for complexity classes. It analyzes relative-saving regimes and their certificate-length boundary, deriving SAT and hierarchy simulations alongside a relativized limit on improving the randomized clock. Its ordinary second-level collapse target for d > 1 remains unproved.

  • Problem

    The paper examines the consequences of membership comparators whose output excludes a possible membership vector or beats uniform guessing by a relative saving.

    Source: §1 · p. 6
  • Method

    It separates comparator regimes by their guaranteed relative saving and analyzes how the resulting heavy-output certificate length affects advice transfer.

    Source: §1 · p. 6, §13.6 · p. 44
  • Results

    The paper gives PH a uniform randomized 2^O(λ(n)^(d^2)) clock and polynomial-length symmetric verification, and derives hierarchy equalities including QH = BPQP and UEXP = EXP.

    Source: §14 · p. 45
  • Takeaways & Limitations

    A layered oracle shows that deterministic comparability and NP^A = coNP^A can coexist with lower bounds against randomized NP clocks of smaller logarithmic power.

    Source: §14 · p. 45

    For d > 1, the ordinary second-level target PH = Σ2^p remains unproved.

    Source: §14 · p. 46

Abstract

from arXiv · show

We study the consequences of membership comparators that exclude one possible membership vector, deterministically or with a relative advantage over uniform guessing. For every polynomially bounded arity, a randomized polynomial-time comparator of error at most $(1-1/poly(n))2^{-t}$ gives $ NP/ poly\cap coNP/ poly$ recognition with common advice. The proof uses limited independence, polynomial occurrence certificates, and a self-contained positive-relation advice transfer. For SAT at arity $O((\log n)^d)$, both this relative-gap hypothesis and deterministic comparability imply $PH=S^{NP}$, the uniform bound $PH\subseteq BPTIME(2^{O((\log n)^{d^2})})$, and symmetric verification with polynomial-length certificates and an oracle-free deterministic $2^{O((\log n)^d)}$ predicate. Polynomial-advice deterministic decoding has the same exponent $d$. Applying the randomized simulation to an unconditional diagonal language yields, for every fixed $\varepsilon>0$, $\mathrm{BPP}\subsetneq BPTIME(2^{O((\log n)^{d^2+\varepsilon})})$, without advice. The larger clock remains subexponential under every fixed number of self-compositions. A layered oracle satisfies deterministic comparability and $NP^O=coNP^O$ but excludes randomized NP algorithms with smaller logarithmic power, establishing a relativized limit on the SAT exponent $d$. This expanded version also develops the full weak-advantage regime, where saving $2^{-O((log n)^d)}$ gives randomized SAT exponent $d$ and PH exponent $d^k$ at fixed level $k$; the quasipolynomial and exponential hierarchy consequences; binary-comparator advice bounds; and the certificate-length boundary between the randomized regimes. Under deterministic comparability, uniform deterministic promise-unique search additionally gives $UEXP=EXP$. The ordinary second-level collapse $PH=\Sigma_2^p$ for $d>1$ remains unproved.

1 Scope, conventions, and main conclusions

The paper studies what deterministic and randomized membership comparability imply for SAT and complexity classes, distinguishing uniform time, predicate time, witness length, and advice. Under the polylogarithmic deterministic hypothesis Hd, it gives promise-unique search and polynomial-hierarchy simulations while leaving the ordinary second-level collapse for d > 1 unproved.

Main conclusions

  • Hd gives UniqueCircuitSAT a deterministic 2^O(λ(n)^d)-time algorithm.The hypothesis uses one deterministic polynomial-time comparator for tuples of arity at least c0λ(n)^d.Source: §1 · pp. 4–5
  • The exponent d2 is independent of the PH level; every language in PH has a symmetric-alternation characterization using polynomial-length certificates and a deterministic predicate of exponent d.Source: §1 · p. 5
  • Hd also yields QH = BPQP, EXPH = BPEXP, NEXP = REXP, and UEXP = EXP.These hierarchy equalities are listed among the theorem’s consequences.Source: §1 · p. 5

Open boundary

  • For d > 1, the predicate remains permitted to run in quasipolynomial time, while its quantified strings are polynomial-length and its exponent is d, not d2.Source: §1 · p. 5

Oracle limit

  • A layered oracle satisfies the comparability threshold and NP^A = coNP^A while ruling out randomized NP algorithms with smaller logarithmic-power clocks.The result limits improvements to the randomized SAT clock that relativize.Source: §1 · p. 6

Randomized comparability

  • Randomized comparators are treated in two regimes distinguished by the guaranteed relative saving over uniform guessing.In the weak-saving regime, SAT retains randomized exponent d and PH has exponent dk at fixed level k; whether this regime implies NP ⊆ coNP/poly remains unresolved.Source: §1 · p. 6

2 A parameter-explicit promise-unique algorithm

The section gives a parameter-explicit reconstruction algorithm for promise-unique circuit satisfiability, preserving the logarithmic exponent of deterministic membership comparability. Its search version returns only verified assignments and finds the witness on uniquely satisfiable inputs.

2 A parameter-explicit promise-unique algorithm

  • Sauer–Shelah bounds the surviving field values when no K-coordinate set is shattered, and Sudan reconstruction lists polynomials agreeing on enough pairs.The proof applies the general shortlist bound to exclusions of one prescribed pattern on each K-subset.Source: §2 · pp. 6–7
  • 2^O((log N)^d) time suffices for deterministic UniqueCircuitSAT decision and search under H_d.The search returns a verified assignment or ⊥ on every circuit, and returns the unique witness on uniquely satisfiable circuits.Source: §2 · p. 7
  • Coordinate-subset exclusions shortlist field values, and polynomial list reconstruction recovers the unique satisfying assignment.The true polynomial appears in the reconstructed list because it agrees with enough evaluation pairs; each candidate is checked directly in the circuit.Source: §2 · p. 8
  • 2^O(m) time covers field construction, enumeration, reconstruction, and verification, including on off-promise inputs.Since m = Θ((log N)^d), the resulting clock is 2^O((log N)^d).Source: §2 · pp. 7–8
  • The rescaling uses field degree Θ((log N)^d) while preserving exponent d through the SAT reductions.The polynomial-evaluation encoding, coordinate shortlisting, and list reconstruction follow Sivakumar.Source: §2 · pp. 7–8

3 Uniform isolation without advice

Linear-seed isolation turns a deterministic promise-unique solver into a uniform randomized CircuitSAT algorithm without advice. It preserves the solver’s asymptotic time bound and has one-sided error.

3 Uniform isolation without advice

  • The resulting CircuitSAT algorithm has one-sided error and the same 2^O((log N)^d) time bound.Before constant amplification, satisfiable circuits are accepted with probability at least 3/16; unsatisfiable circuits are always rejected.Source: §3 · p. 9
  • A Toeplitz matrix and independent shift provide pairwise-independent hash values using a seed of length 3w + 1.The algorithm tests every restriction prefix and accepts if the promise solver accepts any restricted circuit.Source: §3 · p. 9
  • Testing every prefix avoids the factor-w success loss from choosing a single prefix length.For a nonempty satisfying set, the analysis chooses a restriction with a constant probability of leaving one assignment.Source: §3 · p. 9
  • Polynomially many restricted-circuit calls preserve the time bound, and a fixed number of independent seeds raises success probability to at least 2/3.The algorithm samples its random seeds directly and uses no advice.Source: §3 · p. 9

4 From a SAT algorithm to a second-level simulation

The section converts a bounded-error SAT algorithm into a common-random-tape simulation for second-level predicates. Explicitly compiling the randomized computation into a circuit accounts for the resulting exponent d^2 rather than d.

4 From a SAT algorithm to a second-level simulation

  • Every language represented by ∃u ∀v R(x,u,v)=1 has polynomial-length quantifiers and a polynomial-time predicate.The construction also applies by complementation to the corresponding Π_2^p simulation.Source: §4 · p. 10
  • A common amplified random tape makes the predicate computation correct for all candidate u values with high probability.A union bound suffices; independence among answers for different u is unnecessary.Source: §4 · p. 10
  • The method compiles the fixed-tape computation into an explicit circuit and applies the SAT algorithm to that circuit.The circuit hardwires x and the random tape, leaving u as its free input.Source: §4 · p. 10
  • The simulation has exponent d^2 because the final SAT input is a quasipolynomial-length circuit description.The composition does not make that circuit polynomial-size.Source: §4 · p. 10

5 A level-independent simulation of the polynomial hierarchy

Under H_d, the section obtains a uniform randomized simulation of every language in PH with an exponent independent of hierarchy level. The proof simulates a bounded number of adaptive oracle queries while controlling timeout and answer errors.

5 A level-independent simulation of the polynomial hierarchy

  • The section describes S_2 as symmetric alternation with a polynomial-time NP-oracle verifier and polynomial-length certificates for both outcomes.The imported collapse also supplies a zero-error oracle simulation, with expected polynomial time measured against the exact oracle.Source: §5 · p. 11
  • The polynomial-arity advice theorem yields SAT ∈ coNP/poly, which reductions extend to NP ⊆ coNP/poly before applying the strengthened Yap collapse.The cited structural results are imported rather than consequences of the binary-certificate theorem.Source: §5 · pp. 10–11
  • PH is contained in BPTIME(2^O((log n)^d^2)), with exponent d^2 independent of the language’s PH level.The polynomial and hidden constants may depend on the language.Source: §5 · pp. 11–12
  • The proof truncates a zero-error oracle computation, bounds timeout probability, and replaces its adaptive oracle queries with amplified randomized simulations.Coupling to the exact-oracle run and summing first-error probabilities controls divergence across the queries.Source: §5 · pp. 11–12

6 The quasipolynomial hierarchy

Under Hd, the quasipolynomial hierarchy collapses to bounded-error quasipolynomial time. The proof reduces quantified quasipolynomial predicates to circuit satisfiability while accounting for the quantified strings.

6 The quasipolynomial hierarchy

  • A bounded-error quasipolynomial predicate with a quasipolynomial-length existential or universal block can be decided in quasipolynomial time under the CircuitSAT assumption.The proof amplifies error, uses one common random tape, compiles the fixed-tape computation into a circuit, and invokes the assumed circuit-satisfiability algorithm.Source: §6 · p. 12
  • Under Hd, QH = BPQP; the reduction direction applies the quantified-block lemma a fixed number of times.The reverse inclusion is unconditional.Source: §6 · p. 12
  • For the quantified-block reduction, the existential block has length m^2, the universal block has length m, and the predicate runs in quasipolynomial time.The shifts in the covering argument are quantified strings, not free advice.Source: §6 · p. 13
  • The covering argument turns bounded-error acceptance into a second-level quasipolynomial alternating computation.In yes-instances, a collection of m shifts covers the random-tape cube; in no-instances, no such collection covers it.Source: §6 · pp. 12–13

7 Exponential-time padding consequences

Padding and diagonalization yield exponential-hierarchy consequences and unconditional hard languages. Under Hd, those languages also give explicit randomized clocks and an advice-free separation from BPP.

7 Exponential-time padding consequences

  • Under Hd, NEXP = REXP, by encoding a nondeterministic computation as a SAT instance and applying the one-sided randomized SAT algorithm.The reverse inclusion follows by guessing the random tape; one-sided soundness excludes accepting tapes on no-instances.Source: §7 · p. 13
  • Under Hd, UEXP = EXP via a zero-or-one-preserving encoding of unambiguous computations and promise-unique search.The reverse inclusion holds because deterministic machines are unambiguous.Source: §7 · p. 13

7.1 The exponential hierarchy

  • Under Hd, EXPH = BPEXP, using padding to transfer the PH simulation to exponential-time alternating classes.For fixed alternation level k, the padding lemma converts a t(n)-bounded characterization into bounded-error time 2^O((log t(n))^d^2).Source: §7.1 · p. 14

7.2 Unconditional diagonalization and conditional randomized simulation

  • Unconditionally, some H ∈ Σ5E has signed existential circuit lower bounds on every length-m slice for m ≥6.Source: §7.2 · pp. 15–16
  • Prefix projection yields unconditional languages with circuit lower bounds exceeding every fixed polynomial, and a polylogarithmic choice places one such language outside both NP/poly and coNP/poly.The QH containment applies when the prefix length is polylogarithmic; the condition ℓ(n) ≤ n alone does not suffice.Source: §7.2 · pp. 16–17
  • Under Hd, the same unconditional diagonal languages have uniform bounded-error algorithms with clock 2^O((log n)^d^2).For every fixed ε > 0, one such language also yields BPP ⊊ BPTIME(2^O((log n)^(d^2+ε))) without advice.Source: §7.2 · p. 17
  • For every fixed ε > 0, the advice-free separation uses a larger clock that remains subexponential under every fixed number of self-compositions.The result is conditional on Hd and compares uniformly decided languages.Source: §7.2 · pp. 17–18
  • With coNP ⊆ NP/poly, the unconditional language in QH but outside NP/poly separates PH from QH; under Hd, the argument also gives BPQP consequences.This advice-based separation does not require the randomized simulation.Source: §7.2 · pp. 18–19

8 Advice-preserving consequences

Under Hd, time-scaled isolation preserves designated advice while producing a deterministic interpreter. A closure argument then gives every fixed PH language a deterministic simulation with polynomial advice and exponent d.

8 Advice-preserving consequences

  • Under Hd, time-scaled isolation transforms a designated-advice verifier into a deterministic interpreter running in 2^O((log n)^d) time.The resulting advice includes the original designated advice and a walk description that works simultaneously for all inputs of a given length.Source: §8 · pp. 19–20
  • The isolation procedure preserves an explicit advice accounting of O(a(n) + w(n) + n) bits.The walk is ordinary advice fixed for all inputs of that length; it is not a runtime-sampled seed.Source: §8 · pp. 19–20

8.1 A deterministic, level-independent bound for all of PH

  • If coNP ⊆ NP/poly, NP/poly is closed under complementation and polynomial-length existential and universal projection, yielding PH ⊆ NP/poly.The proof bundles designated advice for the relevant input lengths; it does not certify arbitrary choices of the original advice.Source: §8.1 · pp. 20–21
  • Under Hd, each fixed language in PH has a deterministic simulation with polynomial advice and time 2^O((log n)^d), with d independent of the PH level.The advice polynomial and constants may depend on the language.Source: §8.1 · p. 20

9 The completeness obstruction and certified-search elimination

Section 9 explains why soundness-only refutation advice does not establish the needed completeness test, then replaces it with certified witness search. This yields polynomial-length two-block and symmetric simulations of PH with deterministic predicates clocked at 2^O((log n)^d).

9.1 Why soundness-only refutation advice fails

  • Soundness-only advice cannot justify the proposed second-level test: reject-all advice satisfies the designated guarantee yet makes the test accept every input.A sufficient coNP completeness-enforcement predicate would yield a hierarchy collapse, but the paper does not derive one from Hd.Source: §9.1 · pp. 21–22

9.2 Certified search with advice

  • Certified search under Hd never returns an unchecked witness for any advice, while one designated polynomial-length advice succeeds on every satisfiable circuit of a given length.The search runs in 2^O((log N)^d) time with O(N^2) advice; an optional O(N) compression is noted but not used below.Source: §9.2 · pp. 22–23

9.3 Eliminating the final existential block

  • Under Hd, every language in PH has polynomial-length existential and universal blocks with a deterministic, oracle-free predicate clocked at 2^O((log n)^d), independent of its PH level.For d = 1 this gives PH = Σ_2^p; for d > 1 it is a longer-clock simulation, not an ordinary second-level collapse.Source: §9.3 · p. 24
  • The search advice helps produce positive witnesses, not certify absence of refutations; false instances still have an unsatisfiable circuit for every candidate advice.That distinction avoids the completeness test required by the refutation-advice approach.Source: §9.1 · p. 22, §9.3 · p. 24

9.4 Symmetric alternation with competing seed lists

  • Under Hd, PH also has symmetric polynomial-length certificates checked by an oracle-free deterministic predicate in 2^O((log n)^d) time, with exponent independent of the PH level.Two competing seed bundles provide an exact SAT-oracle answer when either bundle is designated.Source: §9.4 · p. 25
  • The symmetric construction needs each prover’s own designated bundle, not a completeness test, and its query induction covers queries chosen adaptively from both certificates and earlier answers.The discussion diagnoses why predetermined-query certificates do not suffice; it does not establish an impossibility for every use of refutation advice.Source: §9.4 · pp. 25–26

10 Weak prediction and the information in exclusions

Section 10 relates distribution-universal weak prediction to exact circuits, examines what information excluded vectors reveal locally, and identifies the condition for polynomial-time certified search. It also specifies which resource-bound improvements the present arguments do not establish.

10.1 Distribution-universal weak prediction already gives circuits

  • An inverse-polynomial advantage for every input distribution implies polynomial-size exact circuits, even without an efficient method for finding the distribution-specific predictors.The proof samples and majority-votes polynomially many circuits from a minimax distribution.Source: §10.1 · pp. 26–27

10.2 A local exclusion-only experiment

  • With polynomially many exclusions and k(n) = ω(log n), the local posterior advantage is superpolynomially small, so this experiment does not supply the inverse-polynomial gap needed for the circuit implication.The experiment uses only the information in arbitrary excluded vectors, not SAT syntax or the comparator’s program.Source: §10.2 · p. 27

10.3 The exact polynomial-time replacement condition

  • A polynomial-time certified-search replacement with polynomial advice is equivalent to polynomial-size search circuits for CircuitSAT, and this condition yields the usual second-level hierarchy collapse.The equivalence concerns this certified-search route and does not accelerate the specific list-reconstruction program.Source: §10.3 · p. 28

10.4 What the resource bounds do not establish

  • The present analysis gives no matching lower bound for the SAT-derived shortlist sizes, and a smaller evaluation-point count alone guarantees no improvement.Other advice, reconstruction methods, or circuit-specific structure are not ruled out.Source: §10.4 · pp. 28–29
  • The uniform randomized exponent remains d^2: applying reconstruction to succinct descriptions requires unrolling a quasipolynomial computation, increasing the explicit input length and comparison arity.An arity bound in succinct input length for the auxiliary language and variants would remove this loss, but is not derived from Hd.Source: §10.4 · p. 29

11 A relativized limit on the reconstruction exponent

A layered oracle makes the complete set membership-comparable and collapses NP to coNP, yet prevents bounded-error randomized NP algorithms from deciding a unary language at smaller logarithmic-power clocks. For arity K(n)=Θ((log n)^d), this gives a relativized limit on improving the randomized SAT exponent d.

11.3 The theorem

  • For K(n)=Θ((log n)^d), a layered oracle satisfies deterministic comparability and NP^A=coNP^A, while a unary language in NP^A requires bounded-error time on the scale of 2^K(n).The lower bound rules out clocks 2^{O((log n)^{d−ε})} for fixed positive ε in the stated range.Source: §11 · p. 30, §11.3 · p. 32, §11.4 · pp. 33–34

11.1 Conventions

  • The oracle conventions require K to be polynomial-time computable, nondecreasing, at least 2, and eventually at most n/2; the SAT application uses K(n)=max{2,⌈c0(log n)^d⌉}.Polynomial reductions between encodings preserve the logarithmic power d.Source: §11.1 · p. 30

11.2 The random oracle

  • The oracle is built level by level so each table entry avoids the true membership vector for its tuple, while entries are conditionally independent given lower-level information.This conditional law supports the construction's comparator and certificate arguments.Source: §11.2 · p. 31

11.3 The theorem

  • A deterministic polynomial-time oracle comparator reads the table vector for the first K(n) tuple coordinates, which necessarily differs from their true membership vector.It pads the output with zeros for any remaining coordinates.Source: §11.3 · p. 31
  • Nonmembership in the complete set has polynomially checkable certificates, and with probability one all sufficiently long unsatisfiable instances have such certificates.The verifier checks K(m) oracle queries; the finite exceptional set is hardwired into a fixed machine.Source: §11.3 · p. 32

11.4 Consequences

  • The relativized lower bound applies to every admissible arity K(n)=ω(log n), with an oracle depending on K, and blocks a general relativizing extension of the logarithmic-arity NP=RP consequence.For K(n)=Θ((log n)^d), it fixes the logarithmic power d, not the leading constant tied to the complete-set encoding.Source: §11.4 · pp. 33–34

12 Randomized comparators

The paper studies randomized membership comparators whose error improves on uniform guessing, then amplifies their signal within a reconstruction procedure. This yields a one-sided randomized SAT algorithm and hierarchy consequences, while the weak-advantage regime leaves some structural and certificate-length questions open.

12.1 Error below a uniform guess

  • The comparator's error is the probability of outputting the one forbidden membership vector, while uniform guessing has error exactly 2^-t.Thus an error allowance at or above that baseline is vacuous for growing arity.Source: §12.1 · p. 34

12.2 Amplification inside the reconstruction clock

  • Mode amplification uses repeated comparator outputs to identify a vector other than the true membership vector with controlled error.The sampling cost is M evaluations, with deterministic mode-counting overhead polynomial in t and log(M+1).Source: §12.2 · p. 35
  • Under weak randomized comparability, randomized reconstruction returns a satisfying assignment or ⊥ within 2^{O((log N)^d)} steps on every circuit and coin sequence.Returned assignments are checked before they are returned, and unsatisfiable circuits always yield ⊥.Source: §12.2 · pp. 35–36
  • A uniquely satisfiable circuit is solved with probability at least 2/3, and isolation converts this into a one-sided randomized SAT algorithm.For d=1, the algorithm is polynomial-time and gives NP=RP.Source: §12.2 · pp. 35–36

12.3 Consequences of weak randomized comparability

  • The weak-regime consequences include PH⊆BPQP, with the exponent allowed to depend on the fixed hierarchy level, and QH=BPQP.The supplied section also states quasipolynomial and exponential hierarchy consequences.Source: §12.3 · pp. 36–37
  • The weak-regime diagonalization places an unconditional language in BPQP but outside BPP, using a fifth-level signed existential diagonal language.That construction also excludes NP/poly and coNP/poly for the corresponding language.Source: §12.3 · pp. 37–38
  • For d>1, whether weak comparability implies NP⊆coNP/poly remains unresolved because a heavy-output certificate can have quasipolynomial length.The stated obstruction is that the positive-relation theorem then lacks a polynomial-time NP/poly verifier.Source: §12.3 · p. 38
  • The oracle lower bound limits improvements to the randomized SAT clock in both randomized regimes, but does not bound the PH exponents d^k or d^2.Relative to that oracle, PH^A=NP^A remains compatible with the lower bound.Source: §12.3 · p. 38

13 Relative-gap comparators via succinct sample tables

This section studies how relative-gap comparators at polylogarithmic SAT arity support sample-table constructions and consequences for randomized search and structural transfers. It distinguishes weaker and stronger savings by the certificate lengths they permit, noting that the boundary limits the method rather than giving a converse.

13.1 Hypothesis and result

  • Hrel_d requires error smaller than uniform-guess error by an inverse-polynomial relative saving at arity at least c0 log^d n.The absolute saving can be smaller than every inverse polynomial when the arity grows faster than log n.Source: §13.1 · p. 39

13.2 Limited independence and local table evaluation

  • An even-moment tail bound for limited-independence indicators suffices because the construction needs only an upper-tail guarantee for each tuple.The centered rth moment matches the fully independent case when the variables are r-wise independent.Source: §13.2 · pp. 39–40

13.3 Certifiable heavy outputs

  • A polynomial-length, locally evaluable limited-independence table makes some wrong output vector occur at least R times on every tuple, while the true vector occurs fewer than R times.The resulting heavy-output relation has polynomial-length occurrence certificates; finding a heavy vector by enumeration can still take 2^k(n) poly(n) time.Source: §13.3 · pp. 40–42

13.4 The positive form of the advice theorem

  • A total relation accepting only incorrect membership vectors and lying in NP/poly transfers SAT recognition to NP/poly and coNP/poly with common polynomial advice.The transfer uses positive certificates for the relation to construct verifiers for both membership bits.Source: §13.4 · p. 42

13.5 Recovering the clocks and the symmetric simulation

  • The transfer yields PH = S^NP and a uniform PH time bound of 2^{O((log n)^{d^2})}, alongside symmetric two-certificate verification using an oracle-free deterministic 2^{O((log n)^d)} predicate.The construction also gives polynomial-advice deterministic decoding at exponent d and certified search with soundness under every candidate advice string.Source: §13.5 · pp. 42–43

The fixed signed-circuit diagonal language G of Corollary 7.6 satisfies

  • Applying the transfer to fixed signed-circuit diagonal language G yields PH/poly = NP/poly = coNP/poly and PH ⊊ QH = BPQP, with BPQP not⊆PH/poly.The fixed-polynomial circuit lower bounds retain exponent d^2.Source: The fixed signed-circuit diagonal… · p. 43

13.6 The certificate-length boundary

  • With only quasipolynomially small relative advantage, occurrence certificates become quasipolynomial rather than polynomial, so this route does not establish NP/poly, though randomized SAT exponent d and fixed-level PH exponent dk remain.Whether this weaker guarantee implies NP ⊆ coNP/poly is left unresolved.Source: §13.6 · p. 44
  • With larger R, polynomial-evaluation and even-moment methods still yield certified SAT search with polynomial advice and exponent d, but not a polynomial-time verifier for the heavy-output relation.The certificate-length threshold is a boundary of this method, not a converse theorem.Source: §13.6 · p. 44
  • For d = 2, saving (n + 2)^−3 gives a polynomial heavy-output certificate and randomized PH exponent 4; saving 2^-Θ(λ(n)^2) gives SAT exponent 2 and kth-level PH exponent 2k.The weaker-saving result does not use the structural advice step.Source: §13.6 · pp. 44–45
  • A saving of 2^-Θ(λ(n)^d) retains randomized SAT exponent d but gives only exponent dk at the kth PH level, without the structural advice step.For d = 1, the weak saving is already inverse-polynomial, so the two regimes coincide up to constants.Source: §13.6 · pp. 44–45
  • Nonuniform table descriptions and the lack of a polynomial-time output selector mean relative-gap transfer gives neither SAT ∈ P/poly nor PH = Σ2^p for d > 1.The deterministic oracle of Section 11 satisfies both randomized hypotheses, so Corollary 11.6 still limits randomized SAT-clock improvements to logarithmic power d.Source: §13.6 · p. 45

14 Summary and status

The section compares the relative-gap and weaker-advantage regimes, their hierarchy and time consequences, and the remaining limits on the results. It also identifies the ordinary second-level collapse as unresolved for d > 1.

Hierarchy consequences

  • Padding yields QH = BPQP, EXPH = BPEXP, NEXP = REXP, and UEXP = EXP; binary-comparator decoding separately retains ordinary linear advice.The uniform randomized PH clock is 2^O((log n)^d^2), independent of hierarchy level, and symmetric certificates have polynomial length.Source: §14 · p. 45

Diagonalization

  • Applying the randomized simulation to the unconditional diagonal language G gives a quantitative, advice-free separation of BPP from larger randomized time classes.The passage states that this implication uses Adleman’s theorem; PH ⊊ QH also follows independently from the advice consequence of Hd.Source: §14 · p. 45

Oracle lower bound

  • A layered oracle satisfies NP^O = coNP^O yet excludes unary NP languages from BPTIME^O(T) when T(n)2^-K(n) tends to zero.For K(n) = ⌈c0(log n)^d⌉ and d ≥ 2, the construction rules out clocks 2^δ(log n)^d for 0 < δ < c0.Source: §14 · p. 45

Relative-gap regime

  • An inverse-polynomial relative saving yields the structural collapse, level-independent randomized PH exponent d^2, and exponent-d symmetric and polynomial-advice simulations.Theorem 13.2 retains the conclusions of Theorem 1.4 except for uniform deterministic promise-unique search and UEXP = EXP.Source: §14 · p. 45

Weak-advantage regime

  • A saving of 2^-O((log n)^d) gives randomized SAT time 2^O((log n)^d), fixed-level PH exponent d^k, and QH = BPQP, EXPH = BPEXP, and NEXP = REXP.For d = 1, the weak saving is already inverse-polynomial, so the two regimes coincide up to constants.Source: §14 · pp. 45–46

Certificate-length boundary

  • The weak-regime occurrence certificate may be quasipolynomially long, so polynomial-advice certified SAT search survives while the positive-relation transfer does not follow.The text describes this certificate-length boundary as a threshold of the method, not a converse theorem.Source: §14 · p. 46

Open boundary

  • For d > 1, the ordinary second-level target PH = Σ2^p remains unproved; the oracle result addresses randomized time improvement instead.In the certified-search route, replacing the search step by polynomial time with polynomial advice is equivalent to SAT ∈ P/poly.Source: §14 · p. 46

A A self-contained positive-relation advice transfer

The appendix gives a self-contained cover-versus-residual proof that transfers a positive relation into common polynomial advice for recognizing both membership and nonmembership. Its verifier uses only positive relation certificates and does not test the construction’s residual property.

Certified relations

  • The proof normalizes W-membership into a deterministic polynomial-time predicate with polynomial-length certificates, then forms relations with truthfully labeled suffixes.Each relation test guesses pool indices and a certificate rather than enumerating the product of the pools.Source: A A self-contained positive-relation… · p. 47

Cover-versus-residual argument

  • At each stage, anchors cover a quarter of the residual set; if all stages are covered, the proof descends to a total one-coordinate relation.If a nonempty residual remains, the construction stops and retains it for the alternative case.Source: A A self-contained positive-relation… · pp. 47–48

Residual case

  • In the residual case, each input has more than three quarters of the residual positions as good positions, where the wrong requested bit has no accepting certificate.The proof samples a fixed list of positions and uses a majority of distinct positions, not an oracle for the truth values of its NP predicates.Source: A A self-contained positive-relation… · pp. 48–49

Majority verification

  • The verifier guesses certificates for h distinct positions and accepts only if all deterministic checks pass, giving completeness for the true bit and soundness for the wrong bit.For the wrong bit, at most h − 1 of the M positions are bad, so no selection of h distinct positions can pass.Source: A A self-contained positive-relation… · pp. 48–49

Resource bounds

  • The advice, witness, and verification time are polynomially bounded, and the verifier has fixed polynomial bounds even on arbitrary candidate advice.The stored advice includes anchor pools and labels, plus the fixed position list in the residual case.Source: A A self-contained positive-relation… · p. 49

Transfer result

  • One common polynomial advice sequence lets a verifier accept (x, b) exactly when b is the membership bit, proving recognition in NP/poly ∩ coNP/poly.The construction never asks the verifier to certify a negative answer about the relation W.Source: A A self-contained positive-relation… · pp. 47, 49
Loading 2609.34952v1…