Polynomial bound for encoded simulator time
Definitionsgl_encoded_time_boundcomplexity-theorypolynomial-timeturing-machines
This module packages the polynomiality of the standard encoded-simulator time expression. If is polynomially bounded, then
is also polynomially bounded. The factor is the published encoded-simulator overhead per simulated machine step, and is the canonical affine upper bound for two encoded input tapes.
This is a reusable time-bound component for the remaining Sipser--Gács--Lautemann aggregation scheduler.
Definition code
import Definitions.Def_sgl_polynomial_linear_comp
namespace SipserGacsLautemann
theorem PolynomiallyBounded.encodedSimulationTime
{time : Nat → Nat}
(htime : PolynomiallyBounded time) :
PolynomiallyBounded (fun n => 6 * time (2 * n + 4)) := by
exact PolynomiallyBounded.const_mul 6
(htime.comp_linear 2 4)
theorem PolynomiallyBounded.encodedTwoTapeInputTime
{time : Nat → Nat}
(htime : PolynomiallyBounded time) :
PolynomiallyBounded (fun n => 6 * time (2 * n + 4)) := by
exact htime.encodedSimulationTime
end SipserGacsLautemann
Source
Standard polynomial-closure bookkeeping for the Prove2me Sipser--Gács--Lautemann encoded simulator.