Convert typed result machines into polynomial-time deciders
Definitionsgl_result_machine_dptcomplexity-theoryleansipser-gacs-lautemannturing-machines
This module packages two structural conversion lemmas for the mission machine model. If a finite typed machine has a polynomial clock and its final result at that clock is exactly some (answer input), then its relabeled toMachine decides the Boolean predicate answer input = true in polynomial time. A second variant handles machines that return some (decide (P input)) and packages them directly as DecidesInPolynomialTime P.
These lemmas are useful for the result-only scheduler obligations in the Sipser--Gács--Lautemann mission, where the hard construction is a finite machine producing a Boolean report and the remaining proof step is converting that report into the standard polynomial-time decider interface.
Definition code
import Definitions.Def_sgl_machine_infrastructure
namespace SipserGacsLautemann
theorem DecidesInPolynomialTime.of_typed_result_bool
{tapes : Nat} {State : Type}
[Fintype State]
(machine : TypedMachine tapes State)
(time : Nat → Nat)
(htime : PolynomiallyBounded time)
(answer : (Fin tapes → List Bool) → Bool)
(hresult :
∀ input : Fin tapes → List Bool,
machine.result
(machine.run input
(time (totalInputLength input))).state =
some (answer input)) :
DecidesInPolynomialTime
(fun input : Fin tapes → List Bool =>
answer input = true) := by
refine
⟨Fintype.card State, machine.toMachine,
time, htime, ?_⟩
intro input
constructor
· rw [machine.toMachine_acceptsWithin_iff]
rw [hresult]
cases hanswer : answer input <;> simp [hanswer]
· rw [machine.toMachine_rejectsWithin_iff]
rw [hresult]
cases hanswer : answer input <;> simp [hanswer]
theorem DecidesInPolynomialTime.of_typed_result_decide
{tapes : Nat} {State : Type}
[Fintype State]
{predicate : (Fin tapes → List Bool) → Prop}
[DecidablePred predicate]
(machine : TypedMachine tapes State)
(time : Nat → Nat)
(htime : PolynomiallyBounded time)
(hresult :
∀ input : Fin tapes → List Bool,
machine.result
(machine.run input
(time (totalInputLength input))).state =
some (decide (predicate input))) :
DecidesInPolynomialTime predicate := by
refine
⟨Fintype.card State, machine.toMachine,
time, htime, ?_⟩
intro input
constructor
· rw [machine.toMachine_acceptsWithin_iff]
rw [hresult]
by_cases h : predicate input <;> simp [h]
· rw [machine.toMachine_rejectsWithin_iff]
rw [hresult]
by_cases h : predicate input <;> simp [h]
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission finite typed-machine infrastructure.