Correctness of one encoded verifier call
Definitionsgl_verifier_call_correctnesscomplexity-theorypolynomial-timeturing-machines
This module specializes the encoded-simulator padded-time correctness theorem to the verifier predicate used in the Sipser--Gács--Lautemann scheduler. Given a concrete two-tape verifier machine for , if the encoded simulator is run on encoded query tapes for any time at least six times the verifier time bound, then accepting is equivalent to and rejecting is equivalent to its negation.
This isolates the final readout step for each scheduled verifier call. The remaining scheduler construction still has to build the encoded query tapes and aggregate many such calls.
Definition code
import Definitions.Def_sgl_encoded_padded_correctness
namespace SipserGacsLautemann
theorem encodedVerifierCall_correctness_at_larger_time
(verifier : List Bool → List Bool → Bool)
{states : Nat}
(machine : Machine 2 states)
(time : Nat → Nat)
(hcorrect :
∀ input : Fin 2 → List Bool,
(machine.acceptsWithin input
(time (totalInputLength input)) ↔
verifier (input 0) (input 1) = true) ∧
(machine.rejectsWithin input
(time (totalInputLength input)) ↔
¬ verifier (input 0) (input 1) = true))
(query : Fin 2 → List Bool)
{later : Nat}
(hle : 6 * time (totalInputLength query) ≤ later) :
(((encodedSimulationTypedMachine machine).toMachine
).acceptsWithin
(fun i => encodeInputBits (query i)) later ↔
verifier (query 0) (query 1) = true) ∧
(((encodedSimulationTypedMachine machine).toMachine
).rejectsWithin
(fun i => encodeInputBits (query i)) later ↔
¬ verifier (query 0) (query 1) = true) := by
exact
encodedSimulation_toMachine_correctness_at_larger_time
machine
(fun input : Fin 2 → List Bool =>
verifier (input 0) (input 1) = true)
query hle (hcorrect query).1 (hcorrect query).2
theorem encodedVerifierCall_accepts_iff
(verifier : List Bool → List Bool → Bool)
{states : Nat}
(machine : Machine 2 states)
(time : Nat → Nat)
(hcorrect :
∀ input : Fin 2 → List Bool,
(machine.acceptsWithin input
(time (totalInputLength input)) ↔
verifier (input 0) (input 1) = true) ∧
(machine.rejectsWithin input
(time (totalInputLength input)) ↔
¬ verifier (input 0) (input 1) = true))
(input random : List Bool)
{later : Nat}
(hle :
6 * time
(totalInputLength
(fun i : Fin 2 =>
if i = 0 then input else random)) ≤ later) :
(((encodedSimulationTypedMachine machine).toMachine
).acceptsWithin
(fun i : Fin 2 =>
encodeInputBits
(if i = 0 then input else random)) later ↔
verifier input random = true) := by
let query : Fin 2 → List Bool :=
fun i => if i = 0 then input else random
have hcall :=
encodedVerifierCall_correctness_at_larger_time
verifier machine time hcorrect query hle
simpa [query] using hcall.1
theorem encodedVerifierCall_rejects_iff
(verifier : List Bool → List Bool → Bool)
{states : Nat}
(machine : Machine 2 states)
(time : Nat → Nat)
(hcorrect :
∀ input : Fin 2 → List Bool,
(machine.acceptsWithin input
(time (totalInputLength input)) ↔
verifier (input 0) (input 1) = true) ∧
(machine.rejectsWithin input
(time (totalInputLength input)) ↔
¬ verifier (input 0) (input 1) = true))
(input random : List Bool)
{later : Nat}
(hle :
6 * time
(totalInputLength
(fun i : Fin 2 =>
if i = 0 then input else random)) ≤ later) :
(((encodedSimulationTypedMachine machine).toMachine
).rejectsWithin
(fun i : Fin 2 =>
encodeInputBits
(if i = 0 then input else random)) later ↔
¬ verifier input random = true) := by
let query : Fin 2 → List Bool :=
fun i => if i = 0 then input else random
have hcall :=
encodedVerifierCall_correctness_at_larger_time
verifier machine time hcorrect query hle
simpa [query] using hcall.2
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; specialization of the published encoded simulator and padded-time correctness lemmas to verifier calls.