Encoded simulator correctness under padded time bounds
Definitionsgl_encoded_padded_correctnesscomplexity-theorypolynomial-timeturing-machines
This module combines two published ingredients: correctness of the encoded simulator on encoded inputs, and preservation of machine correctness under larger time bounds. If a base machine decides a logical predicate on input after exactly simulated steps, then the ordinary relabeled encoded simulator decides the same predicate on encodeInputBits of after any physical time bound at least .
This is directly used by the remaining Sipser--Gács--Lautemann scheduler: a scheduler normally reserves a uniform polynomial number of physical steps for each verifier call, rather than running exactly the verifier stopping time for each query.
Definition code
import Definitions.Def_sgl_encoded_to_machine_adapters
import Definitions.Def_sgl_machine_time_padding
namespace SipserGacsLautemann
theorem encodedSimulation_toMachine_correctness_at_larger_time
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(predicate : (Fin tapes → List Bool) → Prop)
(input : Fin tapes → List Bool)
{exact later : Nat}
(hle : 6 * exact ≤ later)
(hacceptExact :
baseMachine.acceptsWithin input exact ↔ predicate input)
(hrejectExact :
baseMachine.rejectsWithin input exact ↔ ¬ predicate input) :
(((encodedSimulationTypedMachine baseMachine).toMachine
).acceptsWithin
(fun i => encodeInputBits (input i)) later ↔
predicate input) ∧
(((encodedSimulationTypedMachine baseMachine).toMachine
).rejectsWithin
(fun i => encodeInputBits (input i)) later ↔
¬ predicate input) := by
let encodedMachine :=
(encodedSimulationTypedMachine baseMachine).toMachine
have hacceptEncoded :
encodedMachine.acceptsWithin
(fun i => encodeInputBits (input i))
(6 * exact) ↔
predicate input := by
exact
(encodedSimulation_toMachine_acceptsWithin_encoded
baseMachine input exact).trans hacceptExact
have hrejectEncoded :
encodedMachine.rejectsWithin
(fun i => encodeInputBits (input i))
(6 * exact) ↔
¬ predicate input := by
exact
(encodedSimulation_toMachine_rejectsWithin_encoded
baseMachine input exact).trans hrejectExact
exact
encodedMachine.correctness_at_larger_time
(fun _ : Fin tapes → List Bool => predicate input)
(fun i => encodeInputBits (input i))
hle hacceptEncoded hrejectEncoded
theorem encodedSimulation_toMachine_correctness_package_at_larger_time
{tapes baseStates : Nat}
(baseMachine : Machine tapes baseStates)
(predicate : (Fin tapes → List Bool) → Prop)
(exact : (Fin tapes → List Bool) → Nat)
(later : (Fin tapes → List Bool) → Nat)
(hle : ∀ input, 6 * exact input ≤ later input)
(hcorrect :
∀ input : Fin tapes → List Bool,
(baseMachine.acceptsWithin input (exact input) ↔
predicate input) ∧
(baseMachine.rejectsWithin input (exact input) ↔
¬ predicate input)) :
∀ input : Fin tapes → List Bool,
(((encodedSimulationTypedMachine baseMachine).toMachine
).acceptsWithin
(fun i => encodeInputBits (input i)) (later input) ↔
predicate input) ∧
(((encodedSimulationTypedMachine baseMachine).toMachine
).rejectsWithin
(fun i => encodeInputBits (input i)) (later input) ↔
¬ predicate input) := by
intro input
exact
encodedSimulation_toMachine_correctness_at_larger_time
baseMachine predicate input (hle input)
(hcorrect input).1 (hcorrect input).2
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; consequence of the published encoded simulator and deterministic time-padding lemmas.