Build a DPT witness from a concrete machine package
Definitionsgl_dpt_from_machinecomplexity-theorypolynomial-timeutility
This utility repackages the concrete data in the mission definition of deterministic polynomial-time decidability. If a finite-tape machine, a time bound, a proof that the time bound is polynomial, and the accept/reject correctness equivalences are supplied explicitly, then the corresponding predicate satisfies DecidesInPolynomialTime.
It is the converse bookkeeping step to unpacking a DecidesInPolynomialTime hypothesis into its witness machine.
Definition code
import Definitions.Def_sipser_gacs_lautemann
namespace SipserGacsLautemann
theorem DecidesInPolynomialTime.of_machine
{tapes : Nat}
{predicate : (Fin tapes → List Bool) → Prop}
(states : Nat)
(machine : Machine tapes states)
(time : Nat → Nat)
(htime : PolynomiallyBounded time)
(hcorrect :
∀ input : Fin tapes → List Bool,
(machine.acceptsWithin input
(time (totalInputLength input)) ↔
predicate input) ∧
(machine.rejectsWithin input
(time (totalInputLength input)) ↔
¬ predicate input)) :
DecidesInPolynomialTime predicate :=
⟨states, machine, time, htime, hcorrect⟩
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; direct repackaging of the `DecidesInPolynomialTime` definition.