Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.9 — Large gap to an exact decision oracle

Open
NearLogSetCover966.Main.Supplement.theorem_4_9

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover

For every fixed coefficient in the source range 1≤r≤O(log⁡n)1\le r\le O(\log n)1≤r≤O(logn), there is one randomized exact-oracle program with constants independent of the input instance. On n≥1n\ge1n≥1 indexed sets, u≤nu\le nu≤n, any positive budget kkk, and integer rrr in range, it always accepts when opt⁡≤k\operatorname{opt}\le kopt≤k and rejects with probability at least 2/32/32/3 when opt⁡>rk\operatorname{opt}>rkopt>rk. On every run,

#calls≤r(n+1),∣Squery∣≤n,∣Uquery∣≤Cu1/rkmax⁡(1,log⁡2n),\#\mathrm{calls}\le r(n+1),\qquad |S_{\rm query}|\le n,\qquad |U_{\rm query}|\le C u^{1/r}k\max(1,\log_2 n),#calls≤r(n+1),∣Squery​∣≤n,∣Uquery​∣≤Cu1/rkmax(1,log2​n),

and ordinary computation takes C(n+1)eC(n+1)^eC(n+1)e steps. Queries have cover parameter at most kkk 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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me