Length bounds for encoded simulator inputs
Definitionsgl_encoded_length_boundscomplexity-theorypolynomial-timeturing-machines
This module proves elementary size bounds for the published encoded verifier tape format. Each logical tape symbol is encoded by two physical bits, and for every Boolean input list ,
It also lifts this to the total input length of a fixed number of tapes:
for tapes.
This is polynomial-time scheduler bookkeeping: once a loader forms encoded verifier-query tapes, these inequalities connect the encoded-simulator run time to the original logical query lengths.
Definition code
import Definitions.Def_sgl_encoded_simulator
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Tactic
namespace SipserGacsLautemann
theorem encodedSymbolBits_length
(symbol : TapeSymbol) :
(encodedSymbolBits symbol).length = 2 := by
cases symbol with
| blank => rfl
| bit value =>
cases value <;> rfl
theorem encodeInputBits_length_le
(bits : List Bool) :
(encodeInputBits bits).length ≤ 2 * (bits.length + 1) := by
cases bits with
| nil =>
rfl
| cons bit rest =>
simp [encodeInputBits, encodedSymbolBits]
omega
theorem totalInputLength_encodeInputBits_le
{tapes : Nat}
(input : Fin tapes → List Bool) :
totalInputLength
(fun i : Fin tapes => encodeInputBits (input i)) ≤
2 * totalInputLength input + 2 * tapes := by
simp only [totalInputLength, List.sum_ofFn]
calc
(∑ i : Fin tapes,
(encodeInputBits (input i)).length) ≤
∑ i : Fin tapes, 2 * ((input i).length + 1) :=
Finset.sum_le_sum
(fun i _ => encodeInputBits_length_le (input i))
_ = ∑ i : Fin tapes, (2 * (input i).length + 2) := by
apply Finset.sum_congr rfl
intro i _
ring
_ = 2 * (∑ i : Fin tapes, (input i).length) +
2 * tapes := by
rw [Finset.sum_add_distrib]
rw [← Finset.mul_sum]
simp
ring
end SipserGacsLautemann
Source
Direct length calculation for the encoded simulator format in the Prove2me Sipser--Gács--Lautemann mission.