Theorem 4.9 — Large gap to an exact decision oracle
OpenNearLogSetCover966.Main.Supplement.theorem_4_9p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
For every fixed coefficient in the source range , there is one randomized exact-oracle program with constants independent of the input instance. On indexed sets, , any positive budget , and integer in range, it always accepts when and rejects with probability at least when . On every run,
and ordinary computation takes steps. Queries have cover parameter at most and use only exact decision answers. The zero-element input can return YES immediately. This supplies the reverse reduction.
Formalization Note Binary encodings and the inherited finite incidence and actual-machine conventions are used. All resource witnesses are uniform as specified above.
Differences from the source:
- encoding: integer gamma at most O(log n), O(gamma n) oracle calls and O(u^(1/gamma) k log n) query elements → integer r, arbitrary fixed coefficient L, exact call cap r(n+1), and max(1,log n); reason: the call cap is from the source proof; the n=1 case is finite and direct
- encoding: exact decision oracle and polynomial additional time → adaptive machine transcripts with separate counters and resource bounds on every path and query; reason: deletion self-reduction is charged; no witness is supplied by the oracle
- encoding: arbitrary positive input budget k → input order instance, round count, unary k; queries may use min(k,n); reason: after n bits of the final budget field the machine can cap k without scanning an unbounded unary tail, preserving both promise implications
Preamble
import Definitions.Def_NearLogSetCover966_Main_Supplement_Tradeoff set_option autoImplicit false
Formal statement
namespace NearLogSetCover966.Main.Supplement
/-- Theorem 4.9. Every fixed coefficient in γ=O(log n) is permitted;
constants may depend on that fixed coefficient, never on a particular instance. -/
theorem theorem_4_9 :
∀ L : ℝ, 0 < L → ∃ (C : ℝ) (e : ℕ) (P : OracleProgram), 0 < C ∧
∀ (I : SCInstance) (k r : ℕ), 1 ≤ I.sets.length → I.n ≤ I.sets.length →
1 ≤ k → 1 ≤ r → (r : ℝ) ≤ L * max 1 (log2 I.sets.length) →
let x := sampleInput I k r
let B := C * (I.sets.length+1 : ℝ)^e
let Q := (r * (I.sets.length+1) : ℕ)
P.bounded x B Q (queryBound I.sets.length
(C * (I.n : ℝ)^(1/(r : ℝ)) * k * max 1 (log2 I.sets.length)) k) ∧
(coverSmall I k → ∀ ω, P.output x B Q ω = [true]) ∧
(coverLarge I (r*k) → P.prob x B Q (· = [false]) ≥ 2/3) := by sorry
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorem 4.9, printed p.21 (PDF p.23)