Operational fair-coin programs
DefinitionNearLogSetCover966_Main_Supplement_Randomp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
A randomized program consists of two finite, well-formed transition tables on the same tapes and states. At each step an independent fair bit selects the transition table. For an input string and a real time bound , all bit paths are considered. Halting is required on every path, and event probabilities are
The transition tables contain no correctness or halting certificate. The horizon is external to the machine, preventing its length from supplying advice. This extends the inherited actual-machine model with random transitions.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Complexity
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
/-- Two finite transition tables, chosen by a fresh fair bit at each ordinary step.
Only syntactic machine well-formedness is stored, never halting or correctness. -/
structure RandomProgram where
zero : Program
one : Program
sameTapes : one.tapes = zero.tapes
sameStates : one.machine.length = zero.machine.length
abbrev Str := List Bool
def RandomProgram.run (P : RandomProgram) (x : Str) (ω : ℕ → Bool) : ℕ → CookLevin.Config
| 0 => CookLevin.startConfig2 P.zero.tapes (CookLevin.boolsToSymbols x) []
| t + 1 => CookLevin.exe (if ω t then P.one.machine else P.zero.machine) (P.run x ω t)
def coinAt {b : ℕ} (ω : Bits b) (t : ℕ) : Bool := if ht : t < b then ω ⟨t, ht⟩ else false
noncomputable def probability (b : ℕ) (E : Bits b → Prop) : ℝ :=
((Finset.univ.filter fun ω => @decide (E ω) (Classical.propDecidable _)).card : ℝ) / 2 ^ b
noncomputable def RandomProgram.halts (P : RandomProgram) (x : Str) (B : ℝ) : Prop :=
∀ ω : Bits ⌊B⌋₊, (P.run x (coinAt ω) ⌊B⌋₊).1 = P.zero.machine.length
noncomputable def RandomProgram.output (P : RandomProgram) (x : Str) (B : ℝ)
(ω : Bits ⌊B⌋₊) : Str :=
CookLevin.outputOf P.zero.tapes (P.run x (coinAt ω) ⌊B⌋₊) (⌊B⌋₊ + 2)
noncomputable def RandomProgram.prob (P : RandomProgram) (x : Str) (B : ℝ)
(E : Str → Prop) : ℝ := probability ⌊B⌋₊ (fun ω => E (P.output x B ω))
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), §2.1, Hypothesis 2.2, printed p.9 (PDF p.11); §4, printed pp.16–23 (PDF pp.18–25)