Universe–gap domains and two operational reductions
DefinitionNearLogSetCover966_Main_Supplement_Tradeoffp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
The amplification domain records the polynomial lower relation between and , the exact two upper bounds for , and the trivial small-universe cases. The tradeoff domain is
The equivalence predicate requires one forward many-one randomized program and one reverse adaptive exact-oracle program. It records all instance, gap, parameter, universe, time, call-count and success clauses of Corollary 4.10. Its constants are uniform over instances. Reverse queries use , parameters at most and universe at most ; forward parameters are at most . It is a predicate to be proved, never a certificate bundled into machine data.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_Promises
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
noncomputable def amplifyInput (I : SCInstance) (k : ℕ) (γ : ℝ) : Str :=
coverInput I k ++ thresholdCode (γ * (17*k : ℕ))
/-- The u₀=0,1 branches do not divide by log u₀. The lower polynomial growth
has a single absolute coefficient/exponent, before all inputs. -/
noncomputable def AmplificationDomain (α : ℝ) (a : ℕ) (I : SCInstance)
(k : ℕ) (ρ γ : ℝ) : Prop :=
1 ≤ k ∧ 1 ≤ I.sets.length ∧ I.n ≤ I.sets.length ∧
(I.n : ℝ)^a ≤ ρ ∧ 2 < ρ ∧ ρ ≤ I.sets.length ∧
1 ≤ γ ∧ (I.n ≤ 1 ∨ γ ≤ α * log2 ρ / log2 I.n) ∧
γ ≤ α * log2 ρ / ((k : ℝ)^2 * log2 (log2 ρ))
/-- The instance is first, the round count second and the cover budget last.
For k>n the algorithm can stop reading its unary tail after n bits and use min(k,n).
This retains arbitrary positive budgets while keeping polynomial overhead in n. -/
def sampleInput (I : SCInstance) (k r : ℕ) : Str := frame (scEncode I) ++ unary r ++ unary k
noncomputable def TradeoffDomain (n u k : ℕ) (γ : ℝ) : Prop :=
1 ≤ k ∧ 2 < n ∧ 2 < u ∧ u ≤ n ∧ 1 ≤ γ ∧
γ ≤ log2 u / log2 (log2 n) ∧
γ ≤ log2 u / ((k : ℝ)^2 * log2 (log2 u))
noncomputable def forwardInput (I : SCInstance) (k u : ℕ) (γ : ℝ) : Str :=
coverInput I k ++ unary u ++ thresholdCode (γ * (17*k : ℕ))
/-- Both directions of the universe–gap equivalence, with their allowed constant
rescalings and computable parameter bounds. This is a property, never algorithm data.
The forward reduction is many-one; the reverse is adaptive and uses the exact oracle.
The gap floor at 1 handles bounded γ by an exact identity branch. -/
noncomputable def UniverseGapEquivalence (a C : ℝ) (e : ℕ)
(P : RandomProgram) (R : OracleProgram) : Prop :=
0 < a ∧ 0 < C ∧
(∀ n u k : ℕ, ∀ γ : ℝ, TradeoffDomain n u k γ →
∀ I : SCInstance, I.sets.length = n → (I.n : ℝ) ≤ (u : ℝ)^(1/γ) →
let x := forwardInput I k u γ
let B := C * (n+1 : ℝ)^e
P.halts x B ∧
(∀ ω, ∃ J K, P.output x B ω = coverInput J K ∧ 1 ≤ K ∧ K ≤ 17*k ∧
J.sets.length ≤ 34*k*n ∧ J.n ≤ u ∧
(coverSmall I k → coverSmall J K)) ∧
(coverLarge I k → P.prob x B (fun y => ∃ J K, y = coverInput J K ∧
coverLarge J (max 1 (a*γ) * K)) ≥ 2/3)) ∧
(∀ n u k : ℕ, ∀ γ : ℝ, TradeoffDomain n u k γ →
∀ I : SCInstance, I.sets.length = n → I.n ≤ u →
let x := sampleInput I k ⌊γ⌋₊
let B := C * (n+1 : ℝ)^e
let Q := C * γ * n
R.bounded x B Q (queryBound n (C * (u : ℝ)^(4/γ)) k) ∧
(coverSmall I k → ∀ ω, R.output x B Q ω = [true]) ∧
(coverLarge I (γ*k) → R.prob x B Q (· = [false]) ≥ 2/3))
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorems 4.7, 4.9 and Corollary 4.10, printed pp.20–23 (PDF pp.22–25)