Corollary 4.10 — Universe–gap equivalence
OpenNearLogSetCover966.Main.Supplement.corollary_4_10For all , positive and real gaps in the full meaningful range
there are two uniform randomized reductions. Exact cover on sets and universe at most maps to an -gap instance with parameter , sets and universe at most , in polynomial time, with perfect completeness and constant soundness. Conversely, the -gap problem reduces adaptively to exact cover with at most sets per query, universe , calls and polynomial ordinary time; completeness is perfect and soundness at least . Together these are the randomized FPT Turing equivalence with the source's constant rescalings. Both directions are required in the equivalence predicate.
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: O(k), O(kn), Omega(gamma) and u^O(1/gamma) → forward parameter at most 17k, at most 34kn sets, gap max(1,a gamma); reverse universe C u^(4/gamma); reason: the proof supplies the forward constants and r=floor gamma≥gamma/2, log n≤u^(1/gamma), k≤log n give exponent 4 with an absolute multiplier
- encoding: real gamma and meaningful logarithms → real gamma retained, n,u>2, exact finite thresholds and reverse round count floor gamma; reason: no rational-only gap or rounded weaker semantic NO threshold is substituted; undefined logarithmic cases are excluded
- encoding: randomized FPT Turing equivalence → a conjunction of both operational reductions and their computable parameter bounds; reason: the many-one forward program is a one-call Turing reduction; reverse queries have parameter at most k, and the displayed bounds give FPT ordinary time
import Definitions.Def_NearLogSetCover966_Main_Supplement_Tradeoff set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
/-- Both bullets and the randomized FPT Turing equivalence, with real γ and r=floor γ. -/
theorem corollary_4_10 :
∃ (a C : ℝ) (e : ℕ) (P : RandomProgram) (R : OracleProgram),
UniverseGapEquivalence a C e P R := by sorry
end NearLogSetCover966.Main.Supplement