Effective gaps and VC-restricted promises
DefinitionNearLogSetCover966_Main_Supplement_Promisesp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
An admissible real-valued effective gap uses the published rational-approximation interface and satisfies, eventually with a computable threshold,
The VC-restricted promise has YES condition , strict NO condition , polynomial universe, and both stated VC inequalities with uniform constants. The separate fine-grained solver predicate has universe at most , the same logarithmic gap, actual worst-case time , and two-sided success at least . Invalid strings are outside the promise. The growth condition for the base mission's budget is not imposed on .
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_VC
import Definitions.Def_NearLogSetCover966_Main_Supplement_OV
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
noncomputable def vcThreshold (α : ℝ) (k N : ℕ) : ℝ :=
α * log2 N / ((k : ℝ)^2 * log2 (log2 N))
/-- γ has its own admissibility range, without the lower growth condition for ρ. -/
def AdmissibleGap (α : ℝ) (γ : ℕ → ℕ → ℝ) : Prop :=
EffectiveBudget γ ∧ ∃ threshold : ℕ → ℕ, Computable threshold ∧
∀ k N, 1 ≤ k → max 4 (threshold k) ≤ N → 1 ≤ γ k N ∧ γ k N ≤ vcThreshold α k N
noncomputable def vcDomain (α C : ℝ) (e : ℕ) (γ : ℕ → ℕ → ℝ)
(I : SCInstance) (k : ℕ) : Prop :=
1 ≤ k ∧ 4 ≤ I.sets.length ∧ 1 ≤ γ k I.sets.length ∧
γ k I.sets.length ≤ vcThreshold α k I.sets.length ∧
(I.n : ℝ) ≤ C * (I.sets.length : ℝ)^e ∧
(primalVC I : ℝ) ≤ C * (k : ℝ)^2 * γ k I.sets.length * log2 (k * γ k I.sets.length) ∧
(dualVC I : ℝ) ≤ C * k * γ k I.sets.length
noncomputable def vcPromise (α C : ℝ) (e : ℕ) (γ : ℕ → ℕ → ℝ) : DetParamSVP.PromiseProblem where
yes := fun x k => ∃ I, scDecode x = some I ∧ vcDomain α C e γ I k ∧ coverSmall I k
no := fun x k => ∃ I, scDecode x = some I ∧ vcDomain α C e γ I k ∧ coverLarge I (γ k I.sets.length * k)
/-- The fine-grained problem has the exact same semantic gap and universe ≤ number of sets. -/
noncomputable def fineDomain (α : ℝ) (I : SCInstance) (k : ℕ) : Prop :=
1 ≤ k ∧ 4 ≤ I.sets.length ∧ I.n ≤ I.sets.length ∧ 1 ≤ vcThreshold α k I.sets.length
noncomputable def FineSolver (α ε : ℝ) (T : ℕ → ℕ) (P : RandomProgram) (threshold : ℕ → ℕ) : Prop :=
∀ I : SCInstance, ∀ k : ℕ, fineDomain α I k → threshold k ≤ I.sets.length →
let B := (T k : ℝ) * (I.sets.length : ℝ) ^ (ε * k)
P.halts (coverInput I k) B ∧
(coverSmall I k → P.prob (coverInput I k) B (· = [true]) ≥ 2/3) ∧
(coverLarge I (vcThreshold α k I.sets.length * k) →
P.prob (coverInput I k) B (· = [false]) ≥ 2/3)
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorem 4.8, printed pp.20–21 (PDF pp.22–23); Theorem 5.4, printed p.25 (PDF p.27)