Explicit-bound amplification-depth ternary scheduler
ProvedSipserGacsLautemann.ternary_amplification_scheduler_reports_base_accepts_with_explicit_boundcomplexity-theoryproof-engineeringturing-machines
Fix a two-tape verifier machine and explicit natural constants coefficient and degree. This theorem asserts the existence of a two-tape scheduler for the fixed amplification-depth ternary majority construction.
On input tapes (x, R), set
The scheduler returns the ternary majority over the L length-r leaves decoded from R, where each leaf vote is whether the base machine accepts the corresponding two-tape query within the explicit time
This is the concrete computable-step scheduler obligation for the SGL majority-amplification construction.
Preamble
import Definitions.Def_sgl_ternary_machine_vote_data import Definitions.Def_sgl_machine_infrastructure
Formal statement
namespace SipserGacsLautemann
theorem ternary_amplification_scheduler_reports_base_accepts_with_explicit_bound
(states : Nat)
(machine : Machine 2 states)
(coefficient degree : Nat) :
∃ (State : Type) (_ : Fintype State)
(scheduler : TypedMachine 2 State)
(schedulerTime : Nat → Nat),
PolynomiallyBounded schedulerTime ∧
∀ input : Fin 2 → List Bool,
scheduler.result
(scheduler.run input
(schedulerTime (totalInputLength input))).state =
some
(let d := amplificationDepthConstruction (input 0).length
let leafCount := 3 ^ d
let randomBits := (input 1).length / leafCount
ternaryVoteConstruction
(fun random : List Bool =>
@decide
(machine.acceptsWithin
(ternaryTwoTapeInput input random)
(coefficient *
(totalInputLength input + 1) ^ degree))
(Classical.propDecidable _))
d
(ternaryListTreeConstruction
randomBits d (input 1))) := by
sorry
end SipserGacsLautemannSource
Proof-engineering lemma for the Sipser--Gacs--Lautemann Prove2me mission; isolates the explicit-time finite scheduler construction needed for ternary majority amplification.