Theorem 5.4 — Unconditional W[1]-hardness with both VC bounds
OpenNearLogSetCover966.Main.Supplement.theorem_5_4p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
There are absolute constants and a fixed exponent such that for every FPT-computable real gap satisfying the source admissible eventual range,
the -gap -Set Cover promise is W[1]-hard under deterministic FPT many-one reductions on exactly indexed sets with
The same promise contains all three restrictions simultaneously. No complexity-separation assumption is made. This is the bounded-VC companion theorem.
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: FPT-computable real gamma in the stated asymptotic range → published EffectiveBudget approximation interface with its own computable admissibility threshold; reason: the lower growth condition for rho, monotonicity and integer-only gaps are not imposed
- encoding: polynomial universe, both VC O bounds, and W[1]-hardness → one C,e before all gaps and instances, and the existing deterministic PromiseW1Hard; reason: the restrictions are simultaneous; the source hardness is unconditional, with finite indexed sets and strict NO threshold
Preamble
import Definitions.Def_NearLogSetCover966_Main_Supplement_Promises set_option autoImplicit false
Formal statement
namespace NearLogSetCover966.Main.Supplement
/-- Theorem 5.4 (=1.5). Unconditional deterministic W[1]-hardness with both VC bounds. -/
theorem theorem_5_4 :
∃ (α C : ℝ) (e : ℕ), 0 < α ∧ 0 < C ∧
∀ γ : ℕ → ℕ → ℝ, AdmissibleGap α γ →
DetParamSVP.PromiseW1Hard (vcPromise α C e γ) := by sorry
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorem 5.4, printed p.25 (PDF p.27)