The ternary-majority amplified verifier runs in polynomial time
ProvedSipserGacsLautemann.ternary_amplified_verifier_poly_timeLet be a predicate decided in polynomial time by a deterministic two-tape machine of the mission's model. Form the amplified verifier that, on input and random string , sets the depth , splits into consecutive blocks of bits each (padding with zeros), evaluates at every block, and combines the answers by a uniform depth- tree of majority-of-three gates.
This theorem asserts that the amplified verifier is again decidable in polynomial time. The content is purely computational: the tree has polynomially many leaves, each leaf is one call to the given machine on an input of length at most , and the block extraction plus the majority evaluation are elementary string manipulations. It is the first of the two machine-model closure facts needed by the Sipser–Gács–Lautemann development, and it is what makes exponential error reduction free of charge in the polynomial-time accounting.
import Definitions.Def_sipser_gacs_lautemann import Definitions.Def_sgl_verifier_constructions
namespace SipserGacsLautemann
theorem ternary_amplified_verifier_poly_time
(verifier : List Bool → List Bool → Bool)
(hverifier :
DecidesInPolynomialTime
(fun input : Fin 2 → List Bool =>
verifier (input 0) (input 1) = true)) :
DecidesInPolynomialTime
(fun input : Fin 2 → List Bool =>
ternaryAmplifiedVerifierConstruction verifier
(input 0) (input 1) = true) := by sorry
end SipserGacsLautemann