Same-tape preprocessing delegate for polynomial-time machines
Definitionsgl_preprocess_delegateThis module proves a reusable same-tape preprocessing/delegation theorem for the Sipser--Gács--Lautemann machine model. If a finite typed preprocessing machine rewrites an input into the exact initial configuration of a base deterministic multitape machine, then delegates every later step and result to that base machine, the transformed predicate is decidable in polynomial time. The theorem includes polynomial padding for an externally supplied polynomial bound on the transformed input length.
Definition code
import Definitions.Def_sgl_machine_time_padding
import Definitions.Def_sgl_machine_infrastructure
import Definitions.Def_sgl_polynomial_closures
namespace SipserGacsLautemann
theorem TypedMachine.run_add_steps
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool)
(first extra : Nat) :
machine.run input (first + extra) =
(machine.step^[extra]) (machine.run input first) := by
induction extra with
| zero => simp
| succ extra ih =>
rw [Nat.add_succ, TypedMachine.run, ih]
rw [Function.iterate_succ_apply']
theorem Machine.run_eq_iterate_step_from_initial
{tapes states : Nat}
(machine : Machine tapes states)
(input : Fin tapes → List Bool)
(steps : Nat) :
machine.run input steps =
(machine.step^[steps])
(initialConfiguration machine input) := by
induction steps with
| zero => rfl
| succ steps ih =>
rw [Machine.run, ih]
rw [Function.iterate_succ_apply']
theorem preprocessDelegate_iterate_embed
{tapes states : Nat} {State : Type}
(preMachine : TypedMachine tapes State)
(baseMachine : Machine tapes states)
(embed : Configuration tapes states →
TypedConfiguration tapes State)
(hstep :
∀ configuration : Configuration tapes states,
preMachine.step (embed configuration) =
embed (baseMachine.step configuration))
(configuration : Configuration tapes states)
(steps : Nat) :
(preMachine.step^[steps]) (embed configuration) =
embed ((baseMachine.step^[steps]) configuration) := by
induction steps generalizing configuration with
| zero => rfl
| succ steps ih =>
rw [Function.iterate_succ_apply]
rw [hstep]
rw [Function.iterate_succ_apply]
exact ih (baseMachine.step configuration)
theorem preprocessDelegate_run_after_preprocess
{tapes states : Nat} {State : Type}
(preMachine : TypedMachine tapes State)
(baseMachine : Machine tapes states)
(transform :
(Fin tapes → List Bool) → (Fin tapes → List Bool))
(preTime : Nat → Nat)
(embed : Configuration tapes states →
TypedConfiguration tapes State)
(hpre :
∀ input : Fin tapes → List Bool,
preMachine.run input (preTime (totalInputLength input)) =
embed (initialConfiguration baseMachine
(transform input)))
(hstep :
∀ configuration : Configuration tapes states,
preMachine.step (embed configuration) =
embed (baseMachine.step configuration))
(input : Fin tapes → List Bool)
(baseSteps : Nat) :
preMachine.run input
(preTime (totalInputLength input) + baseSteps) =
embed (baseMachine.run (transform input) baseSteps) := by
rw [preMachine.run_add_steps]
rw [hpre]
rw [preprocessDelegate_iterate_embed
preMachine baseMachine embed hstep]
rw [← Machine.run_eq_iterate_step_from_initial]
theorem PolynomiallyBounded.padded_composed_bound
{argument : Nat → Nat}
(hargument : PolynomiallyBounded argument)
(coefficient degree : Nat) :
PolynomiallyBounded
(fun n => coefficient * (argument n + 1) ^ degree) := by
exact
PolynomiallyBounded.const_mul coefficient
((PolynomiallyBounded.succ hargument).pow_const degree)
/-- If a finite preprocessing machine rewrites an input into the exact
initial configuration of a base machine and thereafter delegates each step and
result to that base machine, then the transformed predicate is polynomial-time
decidable. The time bound pads the base machine by a polynomial upper bound on
the transformed input length, so the final clock depends only on the original
input length. -/
theorem DecidesInPolynomialTime.of_same_tape_preprocess_delegate
{tapes states : Nat} {State : Type}
[Fintype State]
{predicate : (Fin tapes → List Bool) → Prop}
(baseMachine : Machine tapes states)
(baseTime : Nat → Nat)
(hbaseTime : PolynomiallyBounded baseTime)
(hbaseCorrect :
∀ input : Fin tapes → List Bool,
(baseMachine.acceptsWithin input
(baseTime (totalInputLength input)) ↔
predicate input) ∧
(baseMachine.rejectsWithin input
(baseTime (totalInputLength input)) ↔
¬ predicate input))
(transform :
(Fin tapes → List Bool) → (Fin tapes → List Bool))
(preMachine : TypedMachine tapes State)
(preTime argumentBound : Nat → Nat)
(hpreTime : PolynomiallyBounded preTime)
(hargumentBound : PolynomiallyBounded argumentBound)
(htransformLength :
∀ input : Fin tapes → List Bool,
totalInputLength (transform input) ≤
argumentBound (totalInputLength input))
(embed : Configuration tapes states →
TypedConfiguration tapes State)
(hpre :
∀ input : Fin tapes → List Bool,
preMachine.run input
(preTime (totalInputLength input)) =
embed (initialConfiguration baseMachine
(transform input)))
(hstep :
∀ configuration : Configuration tapes states,
preMachine.step (embed configuration) =
embed (baseMachine.step configuration))
(hresult :
∀ configuration : Configuration tapes states,
preMachine.result (embed configuration).state =
baseMachine.result configuration.state) :
DecidesInPolynomialTime
(fun input : Fin tapes → List Bool =>
predicate (transform input)) := by
rcases hbaseTime with
⟨coefficient, degree, hbaseBound⟩
let paddedBaseTime : Nat → Nat :=
fun n => coefficient * (argumentBound n + 1) ^ degree
let totalTime : Nat → Nat :=
fun n => preTime n + paddedBaseTime n
let machine := preMachine.toMachine
refine
⟨Fintype.card State, machine, totalTime,
hpreTime.add
(PolynomiallyBounded.padded_composed_bound
hargumentBound coefficient degree),
?_⟩
intro input
let baseInput := transform input
let inputLength := totalInputLength input
let exactBaseSteps := baseTime (totalInputLength baseInput)
let paddedBaseSteps := paddedBaseTime inputLength
have hbaseStepsLe :
exactBaseSteps ≤ paddedBaseSteps := by
dsimp [exactBaseSteps, paddedBaseSteps, paddedBaseTime]
have hlength :
totalInputLength baseInput + 1 ≤
argumentBound inputLength + 1 :=
Nat.succ_le_succ (htransformLength input)
exact
(hbaseBound (totalInputLength baseInput)).trans
(Nat.mul_le_mul_left coefficient
(Nat.pow_le_pow_left hlength degree))
have hbaseCorrectLater :
(baseMachine.acceptsWithin baseInput paddedBaseSteps ↔
predicate baseInput) ∧
(baseMachine.rejectsWithin baseInput paddedBaseSteps ↔
¬ predicate baseInput) := by
exact
baseMachine.correctness_at_larger_time
predicate baseInput hbaseStepsLe
(hbaseCorrect baseInput).1
(hbaseCorrect baseInput).2
have hrun :
preMachine.run input
(preTime inputLength + paddedBaseSteps) =
embed (baseMachine.run baseInput paddedBaseSteps) := by
simpa [baseInput, inputLength, paddedBaseSteps] using
preprocessDelegate_run_after_preprocess
preMachine baseMachine transform preTime embed hpre
hstep input paddedBaseSteps
constructor
· rw [preMachine.toMachine_acceptsWithin_iff]
change
preMachine.result
(preMachine.run input
(totalTime (totalInputLength input))).state =
some true ↔
predicate (transform input)
simp only [totalTime, paddedBaseTime]
rw [hrun]
rw [hresult]
simpa [Machine.acceptsWithin, baseInput,
paddedBaseSteps] using hbaseCorrectLater.1
· rw [preMachine.toMachine_rejectsWithin_iff]
change
preMachine.result
(preMachine.run input
(totalTime (totalInputLength input))).state =
some false ↔
¬ predicate (transform input)
simp only [totalTime, paddedBaseTime]
rw [hrun]
rw [hresult]
simpa [Machine.rejectsWithin, baseInput,
paddedBaseSteps] using hbaseCorrectLater.2
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission internal machine-composition infrastructure.