An answer reduction stage exists for five-level normal form verifiers
ProvedMIPRE.AnswerReduction.nonempty_fiveMIPRE.AnswerReduction ℓ (blueprint thm:answer-reduction) records the data and guarantees of answer reduction for -level verifiers: constants , of the soundness loss ; a threshold ; a polynomial bound and degree deg for the output bound at degree ; the answer-reduced sampler, a function of the input sampler and with polynomial-time program; the polynomial-time compute of the answer-reduced decider from the input programs and ; and the output verifier of level . For an input within the budget at index (sampler and dimension within , decider and accepted answers within , degree ): if the output is within the output bound, rejecting longer answers (complexity); for , and , a value- PCC strategy for gives one for the output at (completeness); for , , and , implies (soundness). The statement: the contract holds at :
The level is the introspective verifier's, and the output is read at levels, as GapCompression.ofPipeline requires. In MIPRE/Background/Pipeline.lean every chapter 7 consequence is stated with an AnswerReduction 5 as its single remaining hypothesis; this leaf is that hypothesis.
Formalization Note In the repository the inhabitant is MIPRE.AnswerReduction.answerReduction, arVerifier over the classical PCP decider TM.CookLevin.Pad.classicalPcpDecider. The contract adapts the paper's absolute-time hypothesis to degrees in the input size, bounds the input sampler's size by too, and keeps the paper's threshold and regime . The platform holds the statement only: the development proves it, in code the platform cannot host yet.
import Mathlib.Algebra.BigOperators.Group.Finset.Basic import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.Polynomial.Eval.Defs import Mathlib.Analysis.CStarAlgebra.CStarMatrix import Mathlib.Analysis.CStarAlgebra.Classes import Mathlib.Analysis.Matrix.Order import Mathlib.Data.ENat.Lattice import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Pi import Mathlib.Data.List.Basic import Mathlib.Data.Nat.Bits import Mathlib.Data.Nat.Notation import Mathlib.Data.Nat.Size import Mathlib.Data.Real.Basic import Mathlib.Data.ZMod.Basic import Mathlib.LinearAlgebra.Matrix.Kronecker import Mathlib.LinearAlgebra.Pi import Definitions.Def_MIPRE_Foundations_CL_Register import Definitions.Def_MIPRE_Foundations_CL_Basic import Definitions.Def_MIPRE_Foundations_CL_Closure import Definitions.Def_MIPRE_Foundations_Cost_Basic import Definitions.Def_MIPRE_Foundations_Cost_Basic_B import Definitions.Def_MIPRE_Foundations_Cost_Encoding import Definitions.Def_MIPRE_Foundations_Cost_Encoding_B import Definitions.Def_MIPRE_Foundations_Cost_PolyTime import Definitions.Def_MIPRE_Foundations_CL_Sampler import Definitions.Def_MIPRE_Foundations_Games import Definitions.Def_MIPRE_Foundations_GameTransport import Definitions.Def_MIPRE_Foundations_GameDouble import Definitions.Def_MIPRE_Foundations_Verifier import Definitions.Def_MIPRE_Foundations_GapCompression import Definitions.Def_MIPRE_Foundations_VerifierValue import Definitions.Def_MIPRE_Foundations_Pipeline_Budget import Definitions.Def_MIPRE_Foundations_Pipeline_AnswerReduction
theorem MIPRE.AnswerReduction.nonempty_five : Nonempty (MIPRE.AnswerReduction 5) := by sorry