Theorem 4.7 — Small universe to large gap
OpenNearLogSetCover966.Main.Supplement.theorem_4_7p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexityset-cover
There are absolute , a fixed integer , an exponent , and one randomized program. For every positive cover budget , finite instance with sets and , and admissible real ,
the program has parameter , between and sets, universe at most , and time at most on every random path (equivalently on the source positive-logarithm domain). Completeness is perfect; each NO input has sound output with probability at least . Empty and singleton universes use their direct branches. This is the forward amplification companion to the inherited hardness goal.
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: K=Theta(k) and Theta(kn) sets → K=17k and set count between 17kn and 34kn; reason: Appendix B gives λ=16; the proof uses K=(1+λ)k and n≤q<2n
- encoding: u0 to a fixed absolute positive power and meaningful logarithmic domain → one absolute integer exponent a≥2 before all inputs; rho>2; reason: the existential absolute lower-growth exponent can be increased to at least 2; for u0≥2 this ensures rho≥4 and keeps the source logarithmic range
- encoding: real gamma and polynomial time → floor(17k gamma) supplied as the finite threshold; actual worst-case C(n+k+1)^e steps; reason: integer cover sizes preserve the strict real gap; for u0≥2 admissibility gives k^2≤alpha log2 n, making this exactly polynomial time in n; no good-code event is assumed
- generalization: logarithmic ratio log rho/log u0 on u0≥2 → also zero/singleton universes with arbitrary positive k, with k charged in the polynomial time bound; reason: direct exact branches preserve every size and gap clause; on the source u0≥2 range the time remains n^O(1), while the extension avoids division by log u0 and can write its Theta(kn) indexed output
Preamble
import Definitions.Def_NearLogSetCover966_Main_Supplement_Tradeoff set_option autoImplicit false
Formal statement
namespace NearLogSetCover966.Main.Supplement
/-- Theorem 4.7: a single program, perfect completeness, and no conditioning on code goodness.
The extra zero/singleton-universe cases charge the parameter in the time bound.
On the source's positive-logarithm domain, a≥2 gives rho≥4, so admissibility
bounds k polynomially in n and this is the source's n^{O(1)} bound. -/
theorem theorem_4_7 :
∃ (α C : ℝ) (a e : ℕ) (P : RandomProgram),
0 < α ∧ 0 < C ∧ 2 ≤ a ∧
∀ (I : SCInstance) (k : ℕ) (ρ γ : ℝ), AmplificationDomain α a I k ρ γ →
let x := amplifyInput I k γ
let B := C * (I.sets.length+k+1 : ℝ)^e
P.halts x B ∧
(∀ ω, ∃ J : SCInstance, P.output x B ω = scEncode J ∧
17*k*I.sets.length ≤ J.sets.length ∧ J.sets.length ≤ 34*k*I.sets.length ∧
(J.n : ℝ) ≤ ρ * log2 I.sets.length ∧
(coverSmall I k → coverSmall J (17*k))) ∧
(coverLarge I k → P.prob x B (fun y => ∃ J : SCInstance,
y = scEncode J ∧ coverLarge J (γ*(17*k : ℕ))) ≥ 1 - 1/(I.sets.length : ℝ)) := by sorry
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorem 4.7, printed p.20 (PDF p.22)