Exact cover oracle and adaptive execution
DefinitionNearLogSetCover966_Main_Supplement_Oraclep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
For an indexed finite incidence instance and an integer , the exact oracle returns the truth value of
An oracle program has distinguished query and resume states. Queries are strings written by the actual machine, and the oracle returns one decision bit. The execution records every query, the ordinary step count, and the number of calls. Bounds require halting, bounded ordinary time, bounded calls, and bounded sizes and parameters for every query on every path. Invalid encodings are answered NO. No covering witness is returned for free.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_Random
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
def coverInput (I : SCInstance) (k : ℕ) : Str := SerialBatchTardy.paramCode (scEncode I) k
/-- The oracle reads a unary parameter followed by the base incidence encoding. -/
def readUnary : Str → Option (ℕ × Str)
| [] => none
| false :: xs => some (0, xs)
| true :: xs => (readUnary xs).map fun r => (r.1 + 1, r.2)
noncomputable def exactOracle (x : Str) : Bool := by
classical
exact match readUnary x with
| none => false
| some (k, xs) => match scDecode xs with
| none => false
| some I => decide (coverSmall I k)
/-- Oracle invocation is a distinguished state. Query writing and all ordinary computation
use the actual transition tables. The answer bit replaces tape 1 and execution resumes.
No witness is supplied by the oracle. -/
structure OracleProgram extends RandomProgram where
queryState : ℕ
resumeState : ℕ
query_lt : queryState < zero.machine.length
resume_lt : resumeState < zero.machine.length
structure OracleConfig where
cfg : CookLevin.Config
queries : List Str
steps : ℕ
noncomputable def OracleProgram.step (P : OracleProgram) (ω : Bool) (S : OracleConfig) : OracleConfig :=
if S.cfg.1 = P.queryState then
let q := CookLevin.outputOf P.zero.tapes S.cfg (S.steps + S.queries.length + 2)
let answer := (CookLevin.contents (CookLevin.boolsToSymbols [exactOracle q]), 0)
⟨(P.resumeState, S.cfg.2.set 1 answer), S.queries ++ [q], S.steps⟩
else if S.cfg.1 = P.zero.machine.length then S
else ⟨CookLevin.exe (if ω then P.one.machine else P.zero.machine) S.cfg,
S.queries, S.steps + 1⟩
noncomputable def OracleProgram.run (P : OracleProgram) (x : Str) (ω : ℕ → Bool) : ℕ → OracleConfig
| 0 => ⟨CookLevin.startConfig2 P.zero.tapes (CookLevin.boolsToSymbols x) [], [], 0⟩
| t + 1 => P.step (ω t) (P.run x ω t)
/-- Ordinary time and calls are counted separately. The horizon is their sum. -/
noncomputable def OracleProgram.trace (P : OracleProgram) (x : Str) (B Q : ℝ)
(ω : Bits (⌊B⌋₊ + ⌊Q⌋₊)) : OracleConfig :=
P.run x (coinAt ω) (⌊B⌋₊ + ⌊Q⌋₊)
noncomputable def OracleProgram.bounded (P : OracleProgram) (x : Str) (B Q : ℝ)
(queryOK : Str → Prop) : Prop :=
∀ ω, let S := P.trace x B Q ω
S.cfg.1 = P.zero.machine.length ∧ (S.steps : ℝ) ≤ B ∧
(S.queries.length : ℝ) ≤ Q ∧ ∀ q ∈ S.queries, queryOK q
noncomputable def OracleProgram.output (P : OracleProgram) (x : Str) (B Q : ℝ)
(ω : Bits (⌊B⌋₊ + ⌊Q⌋₊)) : Str :=
CookLevin.outputOf P.zero.tapes (P.trace x B Q ω).cfg (⌊B⌋₊ + ⌊Q⌋₊ + 2)
noncomputable def OracleProgram.prob (P : OracleProgram) (x : Str) (B Q : ℝ)
(E : Str → Prop) : ℝ :=
probability (⌊B⌋₊ + ⌊Q⌋₊) (fun ω => E (P.output x B Q ω))
/-- Every query is a genuine exact-cover decision question with bounded parameter and size. -/
def queryBound (n : ℕ) (u : ℝ) (k : ℕ) (q : Str) : Prop :=
∃ I j, q = coverInput I j ∧ I.sets.length ≤ n ∧ (I.n : ℝ) ≤ u ∧ j ≤ k
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorem 4.9, printed pp.21–22 (PDF pp.23–24)