Lemma verdictP_apply of the MIP* = RE formalization
ProvedMIPRE.AnswerReduction.verdictP_applyA statement of the module MIPRE.Background.AnswerReduction.DecideProg of the MIP* = RE formalization (commit 70cbf1c of vidick/MIPRE-formalization). The answer-reduced decision, as a program. Piece AR-3e of planning/answer-reduction.md: polynomial-time functions computing the decision on blocks of MIPRE/Background/AnswerReduction/DecideSpec, each with the law that it computes its specification (verdictP_apply for the whole). The type-dependent control is a finite table of the type pair (PolyTimeFun.finiteFunction); the field arithmetic is the introspection stage programs'.
Formal statement. In Lean, with the scope shown:
open MIPRE
open MIPRE.AnswerReduction
open MIPRE.Cost MIPRE.Cost.PolyTimeFun MIPRE.AnswerReduction.StageProg MIPRE.AnswerReduction.Pcp MIPRE.Introspection.FieldLineCheck MIPRE.Introspection.FieldQuestionProgram MIPRE.Introspection.SeededLineProgram MIPRE.Introspection.LineProgram MIPRE.CL.Detyping.Program
theorem MIPRE.AnswerReduction.verdictP_apply (kU m'U : Unary) (descs : List Desc) (chkP chkQ : Bool) (p q : ArTy)
(X Y : Blocks) (a b : BitStr) :
verdictP ((kU, m'U, descs), (chkP, chkQ), (p, q), (X, Y), (a, b)) =
verdictB kU m'U descs chkP chkQ p q X Y a b
Formalization Note MIPRE.AnswerReduction.verdictP_apply is declared in MIPRE/Background/AnswerReduction/DecideProg.lean, lines 386–405. The binders, hypotheses and conclusion are exactly those of the Lean statement above; the uploaded statement elaborates to the same type as the declaration in the repository. The definitions it mentions are those of the published definition bundles of the module's import closure.
import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.BigOperators.Group.Finset.Basic import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.CharP.Algebra import Mathlib.Algebra.CharP.Two import Mathlib.Algebra.Field.ZMod import Mathlib.Algebra.MonoidAlgebra.Basic import Mathlib.Algebra.MvPolynomial.CommRing import Mathlib.Algebra.MvPolynomial.Degrees import Mathlib.Algebra.MvPolynomial.SchwartzZippel import Mathlib.Algebra.Polynomial.Degree.Lemmas import Mathlib.Algebra.Polynomial.Degree.SmallDegree import Mathlib.Algebra.Polynomial.Div import Mathlib.Algebra.Polynomial.Eval.Defs import Mathlib.Algebra.Polynomial.Eval.Degree import Mathlib.Algebra.Polynomial.FieldDivision import Mathlib.Algebra.Polynomial.Monic import Mathlib.Algebra.Polynomial.Roots import Mathlib.Algebra.Polynomial.SpecificDegree import Mathlib.Algebra.Squarefree.Basic import Mathlib.Analysis.CStarAlgebra.CStarMatrix import Mathlib.Analysis.CStarAlgebra.Classes import Mathlib.Analysis.CStarAlgebra.Matrix import Mathlib.Analysis.InnerProductSpace.PiL2 import Mathlib.Analysis.Matrix.Order import Mathlib.Analysis.Matrix.PosDef import Mathlib.Analysis.SpecialFunctions.Complex.Circle import Mathlib.Computability.Primrec.List import Mathlib.Data.ENat.Lattice import Mathlib.Data.Fin.Tuple.Basic import Mathlib.Data.Finset.Image import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Pi import Mathlib.Data.List.Basic import Mathlib.Data.List.OfFn import Mathlib.Data.List.Rotate import Mathlib.Data.Matrix.Mul import Mathlib.Data.Nat.Bits import Mathlib.Data.Nat.Factorization.Basic import Mathlib.Data.Nat.Notation import Mathlib.Data.Nat.Size import Mathlib.Data.Rat.Cast.Order import Mathlib.Data.Real.Basic import Mathlib.Data.Set.Basic import Mathlib.Data.ZMod.Basic import Mathlib.FieldTheory.Finite.Basic import Mathlib.FieldTheory.Finite.Extension import Mathlib.FieldTheory.Finite.GaloisField import Mathlib.FieldTheory.Finite.Trace import Mathlib.FieldTheory.Galois.NormalBasis import Mathlib.FieldTheory.IsAlgClosed.AlgebraicClosure import Mathlib.FieldTheory.KummerExtension import Mathlib.FieldTheory.Minpoly.Finite import Mathlib.LinearAlgebra.Basis.Defs import Mathlib.LinearAlgebra.BilinearForm.Orthogonal import Mathlib.LinearAlgebra.FiniteDimensional.Lemmas import Mathlib.LinearAlgebra.LinearIndependent.Lemmas import Mathlib.LinearAlgebra.Matrix.Circulant import Mathlib.LinearAlgebra.Matrix.Kronecker import Mathlib.LinearAlgebra.Matrix.ToLin import Mathlib.LinearAlgebra.Pi import Mathlib.Logic.Denumerable import Mathlib.Logic.Equiv.Fin.Basic import Mathlib.Logic.Function.Iterate import Mathlib.RingTheory.AdjoinRoot import Mathlib.RingTheory.Coprime.Lemmas import Mathlib.RingTheory.Polynomial.Content import Mathlib.RingTheory.Polynomial.Cyclotomic.Factorization import Mathlib.RingTheory.RootsOfUnity.PrimitiveRoots import Mathlib.RingTheory.Trace.Basic import Mathlib.Tactic import Mathlib.Tactic.DeriveFintype import Mathlib.Tactic.IntervalCases import Mathlib.Tactic.Linarith import Mathlib.Tactic.Ring import Definitions.Def_MIPRE_Foundations_Games import Definitions.Def_MIPRE_Foundations_Distances import Definitions.Def_MIPRE_Background_LIDT_Game import Definitions.Def_MIPRE_Foundations_CL_Register import Definitions.Def_MIPRE_Foundations_CL_Canonical import Definitions.Def_MIPRE_Background_LIDT_CLGame import Definitions.Def_MIPRE_Foundations_CL_Basic import Definitions.Def_MIPRE_Background_LIDT_Presentation import Definitions.Def_MIPRE_Foundations_Cost_Basic_B import Definitions.Def_MIPRE_Foundations_Cost_Encoding_B import Definitions.Def_MIPRE_Foundations_SAT_Circuit import Definitions.Def_MIPRE_Foundations_SAT_Cnf import Definitions.Def_MIPRE_Foundations_Cost_PolyTime import Definitions.Def_MIPRE_Foundations_CL_Closure import Definitions.Def_MIPRE_Foundations_CL_Closure_B import Definitions.Def_MIPRE_Foundations_CL_Sampler import Definitions.Def_MIPRE_Foundations_Verifier import Definitions.Def_MIPRE_Foundations_SAT_Succinct import Definitions.Def_MIPRE_Foundations_SAT_Decoupled import Definitions.Def_MIPRE_Foundations_Cost_Closure import Definitions.Def_MIPRE_Foundations_Cost_Loops_B import Definitions.Def_MIPRE_Foundations_Cost_Fold import Definitions.Def_MIPRE_Foundations_Cost_Unary import Definitions.Def_MIPRE_Foundations_Cost_Numeric_B import Definitions.Def_MIPRE_Foundations_LowDegree_Encoding import Definitions.Def_MIPRE_Foundations_SAT_Pcp import Definitions.Def_MIPRE_Background_AnswerReduction_PcpPresentation import Definitions.Def_MIPRE_Foundations_OracularGame import Definitions.Def_MIPRE_Background_AnswerReduction_Predicate import Definitions.Def_MIPRE_Foundations_Closeness import Definitions.Def_MIPRE_Foundations_PerfectStrategy import Definitions.Def_MIPRE_Foundations_GameTransport import Definitions.Def_MIPRE_Foundations_GameDouble import Definitions.Def_MIPRE_Foundations_OracularSound import Definitions.Def_MIPRE_Foundations_OpBound import Definitions.Def_MIPRE_Foundations_StateDistance import Definitions.Def_MIPRE_Foundations_POVMValue import Definitions.Def_MIPRE_Foundations_CrossConsistency import Definitions.Def_MIPRE_Foundations_PVM import Definitions.Def_MIPRE_Foundations_Commutation import Definitions.Def_MIPRE_Foundations_Dilation import Definitions.Def_MIPRE_Foundations_LowDegree_SchwartzZippel import Definitions.Def_MIPRE_Foundations_Sandwich import Definitions.Def_MIPRE_Foundations_POVMMix import Definitions.Def_MIPRE_Foundations_GameAdapt import Definitions.Def_MIPRE_Foundations_RegisterReindex import Definitions.Def_MIPRE_Foundations_OracularTensor import Definitions.Def_MIPRE_Foundations_OracularComplete import Definitions.Def_MIPRE_Foundations_CL_Embedding import Definitions.Def_MIPRE_Foundations_CL_Graph import Definitions.Def_MIPRE_Foundations_CL_Detyping import Definitions.Def_MIPRE_Foundations_CL_DetypingLaw import Definitions.Def_MIPRE_Foundations_SampledGame import Definitions.Def_MIPRE_Foundations_CL_DetypingGame import Definitions.Def_MIPRE_Foundations_GapCompression import Definitions.Def_MIPRE_Foundations_Cost_Codable_B import Definitions.Def_MIPRE_Foundations_Halting_Descriptions import Definitions.Def_MIPRE_Foundations_OracularTyped import Definitions.Def_MIPRE_Background_AnswerReduction_AnswerFormat import Definitions.Def_MIPRE_Foundations_CL_Product import Definitions.Def_MIPRE_Foundations_CL_Downsize import Definitions.Def_MIPRE_Foundations_CL_TypedSampler import Definitions.Def_MIPRE_Foundations_CL_ProductSampler import Definitions.Def_MIPRE_Background_LIDT_PresentationQueries import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryRepresentation import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryConstants import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotient import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNormalize import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDivision import Definitions.Def_MIPRE_Foundations_Cost_Binary import Definitions.Def_MIPRE_Foundations_SAT_Formula import Definitions.Def_MIPRE_Foundations_SAT_FmlLib import Definitions.Def_MIPRE_Foundations_SAT_Flatten import Definitions.Def_MIPRE_Foundations_Cost_Reader import Definitions.Def_MIPRE_Foundations_SAT_FmlProg import Definitions.Def_MIPRE_Foundations_SAT_ArrayProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryLinear import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryElimination import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasisProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryEchelon import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasis import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySolve import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryMatrixSolve import Definitions.Def_MIPRE_Foundations_Cost_Iterates import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCirculantProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryKernel import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryGroupAlgebra import Definitions.Def_MIPRE_Foundations_LowDegree_FiniteReducedComponents import Definitions.Def_MIPRE_Foundations_LowDegree_IdempotentSplit import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponents import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponentsProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientFrobenius import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientComponents import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientFactors import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryGCD import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryFactorization import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCyclotomicSeed import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySubstitution import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNonresidueLoop import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNonresidueCorrectness import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientOrbit import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryTraceBits import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOrbitPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOrbitDescent import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientTranslation import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCoprimeDegree import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComposedSumPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComposedSumProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOddPrimeProgram import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPrimePowerTrace import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreier import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierTower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierLoop import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryDegreeArithmetic import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryPrimality import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryPrimePower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDegreeFactors import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDegreeDecomposition import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPrimePowerDispatch import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryIrreducibleAssembly import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryIrreducibleConstructor import Definitions.Def_MIPRE_Foundations_LowDegree_Shoup import Definitions.Def_MIPRE_Foundations_LowDegree_ShoupCoefficients import Definitions.Def_MIPRE_Foundations_SAT_QuotientField import Definitions.Def_MIPRE_Foundations_SAT_FieldTrace import Definitions.Def_MIPRE_Foundations_SAT_FieldCoordinates import Definitions.Def_MIPRE_Background_AnswerReduction_Layout import Definitions.Def_MIPRE_Background_AnswerReduction_Family import Definitions.Def_MIPRE_Background_AnswerReduction_TypedGame import Definitions.Def_MIPRE_Background_AnswerReduction_Stages import Definitions.Def_MIPRE_Background_AnswerReduction_StageLists import Definitions.Def_MIPRE_Foundations_Cost_BinaryArithmetic import Definitions.Def_MIPRE_Foundations_Introspection_SeedSelectorProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryFold import Definitions.Def_MIPRE_Foundations_SAT_NormalElementProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryInverse import Definitions.Def_MIPRE_Foundations_Introspection_LineRepresentativeProg import Definitions.Def_MIPRE_Foundations_Cost_BinaryCompare import Definitions.Def_MIPRE_Foundations_Introspection_SeededLineProg import Definitions.Def_MIPRE_Foundations_Cost_TreeBits import Definitions.Def_MIPRE_Foundations_CL_DetypingProgFinite import Definitions.Def_MIPRE_Foundations_CL_DetypingProgParse import Definitions.Def_MIPRE_Foundations_Introspection_BinaryBlockProg import Definitions.Def_MIPRE_Background_AnswerReduction_StageProg import Definitions.Def_MIPRE_Background_LIDT_Adapter_Geometry import Definitions.Def_MIPRE_Background_AnswerReduction_StageCorrect import Definitions.Def_MIPRE_Foundations_CL_DetypingQueries import Definitions.Def_MIPRE_Foundations_CL_DetypingProgBits import Definitions.Def_MIPRE_Foundations_CL_DetypingProgCall import Definitions.Def_MIPRE_Foundations_CL_DetypingProgRoute import Definitions.Def_MIPRE_Foundations_Cost_Machine_B import Definitions.Def_MIPRE_Foundations_Cost_MachineData_B import Definitions.Def_MIPRE_Foundations_Cost_Interpreter_B import Definitions.Def_MIPRE_Foundations_Cost_MachineBound_B import Definitions.Def_MIPRE_Foundations_Cost_Toolkit_B import Definitions.Def_MIPRE_Foundations_Cost_Universal_B import Definitions.Def_MIPRE_Foundations_CL_ProductSamplerProg import Definitions.Def_MIPRE_Foundations_Cost_FiniteEncoding import Definitions.Def_MIPRE_Background_AnswerReduction_PcpSampler import Definitions.Def_MIPRE_Foundations_Introspection_FieldPolynomialProg import Definitions.Def_MIPRE_Foundations_Introspection_FieldLineCheckProg import Definitions.Def_MIPRE_Foundations_Introspection_PauliStageProg import Definitions.Def_MIPRE_Foundations_Introspection_FieldQuestionProg import Definitions.Def_MIPRE_Background_AnswerReduction_DecideSpec import Definitions.Def_MIPRE_Foundations_Cost_SizeProgram import Definitions.Def_MIPRE_Foundations_SAT_PcpFormat import Definitions.Def_MIPRE_Foundations_Halting_Lists_B import Definitions.Def_MIPRE_Foundations_Cost_Growth import Definitions.Def_MIPRE_Foundations_Halting_Arith import Definitions.Def_MIPRE_Foundations_Repeat_Prims import Definitions.Def_MIPRE_Foundations_Repeat_MapLoop import Definitions.Def_MIPRE_Foundations_Repeat_Sampler import Definitions.Def_MIPRE_Foundations_CL_Repeat import Definitions.Def_MIPRE_Foundations_Repeat_Bits import Definitions.Def_MIPRE_Foundations_VerifierValue import Definitions.Def_MIPRE_Foundations_Pipeline_Budget import Definitions.Def_MIPRE_Foundations_Pipeline_Repetition import Definitions.Def_MIPRE_Foundations_Repeat_RepSampler import Definitions.Def_MIPRE_Foundations_Repeat_Dom import Definitions.Def_MIPRE_Foundations_Repeat_SamplerCost import Definitions.Def_MIPRE_Foundations_CL_DetypingProgQueries import Definitions.Def_MIPRE_Foundations_CL_DetypingProgSampler import Definitions.Def_MIPRE_Foundations_CL_DetypingProgCost import Definitions.Def_MIPRE_Foundations_OracularSampler import Definitions.Def_MIPRE_Foundations_CL_DetypingDeciderRoute import Definitions.Def_MIPRE_Foundations_CL_DetypingDeciderProg import Definitions.Def_MIPRE_Foundations_CL_DetypingDecider import Definitions.Def_MIPRE_Foundations_CL_DetypingDeciderGame import Definitions.Def_MIPRE_Foundations_Halting_Serial import Definitions.Def_MIPRE_Foundations_Cost_Kleene_B import Definitions.Def_MIPRE_Foundations_OracularDecider import Definitions.Def_MIPRE_Background_AnswerReduction_DecideProg open MIPRE open MIPRE.AnswerReduction open MIPRE.Cost MIPRE.Cost.PolyTimeFun MIPRE.AnswerReduction.StageProg MIPRE.AnswerReduction.Pcp MIPRE.Introspection.FieldLineCheck MIPRE.Introspection.FieldQuestionProgram MIPRE.Introspection.SeededLineProgram MIPRE.Introspection.LineProgram MIPRE.CL.Detyping.Program
theorem MIPRE.AnswerReduction.verdictP_apply (kU m'U : Unary) (descs : List Desc) (chkP chkQ : Bool) (p q : ArTy)
(X Y : Blocks) (a b : BitStr) :
verdictP ((kU, m'U, descs), (chkP, chkQ), (p, q), (X, Y), (a, b)) =
verdictB kU m'U descs chkP chkQ p q X Y a b := by sorry