Lemma fixedCircuit_describes of the MIP* = RE formalization
ProvedMIPRE.TM.CookLevin.Pad.fixedCircuit_describescomputabilitycook-levinmip-remipre-formalizationturing-machines
A statement of the module MIPRE.TM.CookLevin.PcpBridge of the MIP* = RE formalization (commit 70cbf1c of vidick/MIPRE-formalization). # The raw verifier and its fixed typed clause polynomial
Formal statement. In Lean, with the scope shown:
open MIPRE
open MIPRE.TM
open MIPRE.TM.CookLevin
open MIPRE.TM.CookLevin.Pad
open MIPRE.SAT MIPRE.Cost MIPRE.LowDegree MIPRE.LowDegree.BinaryPolynomial MvPolynomial
theorem MIPRE.TM.CookLevin.Pad.fixedCircuit_describes (D : Decider) (n T Q σ : ℕ) (x y : BitStr)
(hV : Valid D.prog n T Q σ x y) :
(fixedCircuit D.prog n T Q σ x y).DescribesDecider
(pcpParams n T Q σ).m (pcpParams n T Q σ).m D n x y T
Formalization Note MIPRE.TM.CookLevin.Pad.fixedCircuit_describes is declared in MIPRE/TM/CookLevin/PcpBridge.lean, lines 37–41. 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.
Preamble
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.Division import Mathlib.Algebra.MvPolynomial.Rename import Mathlib.Algebra.MvPolynomial.SchwartzZippel import Mathlib.Algebra.MvPolynomial.Variables import Mathlib.Algebra.Order.BigOperators.Group.Finset import Mathlib.Algebra.Order.Group.Abs import Mathlib.Algebra.Order.Group.Int 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.Matrix.Order import Mathlib.Combinatorics.Nullstellensatz import Mathlib.Computability.Language import Mathlib.Computability.Primrec.List import Mathlib.Data.ENat.Lattice import Mathlib.Data.Finset.Max import Mathlib.Data.Fintype.Basic import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Fintype.Option import Mathlib.Data.Fintype.Pi import Mathlib.Data.Fintype.Prod import Mathlib.Data.Fintype.Sigma import Mathlib.Data.Fintype.Sum import Mathlib.Data.Int.Interval 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.Bitwise 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.Sign.Defs import Mathlib.Data.ZMod.Basic import Mathlib.FieldTheory.Finite.Basic import Mathlib.FieldTheory.Finite.Extension import Mathlib.FieldTheory.IsAlgClosed.AlgebraicClosure import Mathlib.FieldTheory.KummerExtension import Mathlib.FieldTheory.Minpoly.Finite 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.Logic.Relation 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.Tactic import Mathlib.Tactic.DeriveFintype import Mathlib.Tactic.Linarith import Mathlib.Tactic.Ring import Definitions.Def_MIPRE_Foundations_Games import Definitions.Def_MIPRE_Foundations_CL_Register import Definitions.Def_MIPRE_Foundations_CL_Basic 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_Foundations_LowDegree_SchwartzZippel import Definitions.Def_MIPRE_Foundations_Cost_Codable_B 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_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_Cost_BinaryArithmetic import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryFold import Definitions.Def_MIPRE_Foundations_Cost_BinaryCompare import Definitions.Def_MIPRE_Foundations_Cost_TreeBits import Definitions.Def_MIPRE_Foundations_Cost_Machine_B import Definitions.Def_MIPRE_Foundations_Cost_MachineData_B import Definitions.Def_MIPRE_Foundations_Cost_MachineBound_B import Definitions.Def_MIPRE_Foundations_Cost_SizeProgram import Definitions.Def_MIPRE_Foundations_SAT_PcpFormat import Definitions.Def_MIPRE_Foundations_Cost_Growth import Definitions.Def_MIPRE_Cslib_Foundations_Data_RelatesInSteps import Definitions.Def_MIPRE_Cslib_Computability_Machines_Turing_MultiTape_Deterministic import Definitions.Def_MIPRE_TM_MultiInput_Deterministic import Definitions.Def_MIPRE_TM_CookLevin_Local import Definitions.Def_MIPRE_Foundations_SAT_Tseitin import Definitions.Def_MIPRE_TM_CookLevin_Tableau import Definitions.Def_MIPRE_TM_Interp_Instr import Definitions.Def_MIPRE_TM_Interp_Machine import Definitions.Def_MIPRE_TM_CookLevin_Layout import Definitions.Def_MIPRE_TM_CookLevin_FieldFml import Definitions.Def_MIPRE_TM_CookLevin_Kinds import Definitions.Def_MIPRE_TM_CookLevin_Families import Definitions.Def_MIPRE_TM_CookLevin_Window import Definitions.Def_MIPRE_TM_CookLevin_FamilyFml import Definitions.Def_MIPRE_TM_Interp_Tape import Definitions.Def_MIPRE_TM_Interp_Reach import Definitions.Def_MIPRE_TM_Interp_Routines import Definitions.Def_MIPRE_TM_Interp_Repr import Definitions.Def_MIPRE_TM_Interp_CopyTree import Definitions.Def_MIPRE_TM_Interp_GetEnv import Definitions.Def_MIPRE_TM_Interp_Desc import Definitions.Def_MIPRE_TM_Interp_Step import Definitions.Def_MIPRE_TM_Interp_InputRoutines import Definitions.Def_MIPRE_TM_Interp_Run import Definitions.Def_MIPRE_Foundations_SAT_Table import Definitions.Def_MIPRE_TM_CookLevin_Params import Definitions.Def_MIPRE_TM_CookLevin_AnsEnd import Definitions.Def_MIPRE_TM_CookLevin_Index import Definitions.Def_MIPRE_TM_CookLevin_Describer import Definitions.Def_MIPRE_TM_CookLevin_LayoutProg import Definitions.Def_MIPRE_TM_CookLevin_FieldProg import Definitions.Def_MIPRE_TM_CookLevin_FamilyProg import Definitions.Def_MIPRE_TM_CookLevin_DescProg import Definitions.Def_MIPRE_TM_CookLevin_Semantics import Definitions.Def_MIPRE_TM_CookLevin_Correct import Definitions.Def_MIPRE_TM_CookLevin_Sound import Definitions.Def_MIPRE_TM_CookLevin_Sat import Definitions.Def_MIPRE_TM_CookLevin_Assemble import Definitions.Def_MIPRE_TM_CookLevin_Link import Definitions.Def_MIPRE_TM_CookLevin_Decoupled import Definitions.Def_MIPRE_TM_CookLevin_DecoupledProg import Definitions.Def_MIPRE_Foundations_SAT_Padding import Definitions.Def_MIPRE_Foundations_SAT_Rename import Definitions.Def_MIPRE_Foundations_SAT_PowerPadding import Definitions.Def_MIPRE_TM_CookLevin_Padded import Definitions.Def_MIPRE_Foundations_SAT_GatePadding import Definitions.Def_MIPRE_TM_CookLevin_ExactPadding import Definitions.Def_MIPRE_TM_CookLevin_PaddingParams import Definitions.Def_MIPRE_TM_CookLevin_PcpParameters import Definitions.Def_MIPRE_TM_CookLevin_PcpPrepare import Definitions.Def_MIPRE_Foundations_SAT_GateProg import Definitions.Def_MIPRE_Foundations_SAT_InputRouting import Definitions.Def_MIPRE_Foundations_SAT_InputRoutingProg import Definitions.Def_MIPRE_Foundations_SAT_CircuitArithmetization import Definitions.Def_MIPRE_Foundations_SAT_GateFieldEval import Definitions.Def_MIPRE_Foundations_SAT_PcpFieldTests import Definitions.Def_MIPRE_Foundations_SAT_CircuitFieldEval import Definitions.Def_MIPRE_Foundations_LowDegree_FiniteVariables import Definitions.Def_MIPRE_Foundations_SAT_FiniteCircuitArithmetization import Definitions.Def_MIPRE_Foundations_SAT_CircuitFieldCorrect import Definitions.Def_MIPRE_TM_CookLevin_PcpVerifier import Definitions.Def_MIPRE_Foundations_LowDegree_ZeroBasis import Definitions.Def_MIPRE_Foundations_SAT_PcpAlgebra import Definitions.Def_MIPRE_Foundations_SAT_PcpBlocks import Definitions.Def_MIPRE_TM_CookLevin_PcpClauses import Definitions.Def_MIPRE_TM_CookLevin_PcpCircuit import Definitions.Def_MIPRE_Foundations_SAT_FieldVectors import Definitions.Def_MIPRE_Foundations_SAT_PcpViewTests import Definitions.Def_MIPRE_TM_CookLevin_PcpBridge open MIPRE open MIPRE.TM open MIPRE.TM.CookLevin open MIPRE.TM.CookLevin.Pad open MIPRE.SAT MIPRE.Cost MIPRE.LowDegree MIPRE.LowDegree.BinaryPolynomial MvPolynomial set_option maxRecDepth 4096
Formal statement
theorem MIPRE.TM.CookLevin.Pad.fixedCircuit_describes (D : Decider) (n T Q σ : ℕ) (x y : BitStr)
(hV : Valid D.prog n T Q σ x y) :
(fixedCircuit D.prog n T Q σ x y).DescribesDecider
(pcpParams n T Q σ).m (pcpParams n T Q σ).m D n x y T := by sorrySource