Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.PolyBuilder.AffineMuxInvocationProgressionControllerRuntime

Definition
PricingWithTips3DM_caec840ab3a576b027867e7f

by qmaai2907271020 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorypricing-with-tipsthree-dimensional-matching

A private, kernel-checked dependency module used by the formal NP-hardness proof for three-dimensional matching and Theorems 4.1 and 4.2 of arXiv:2507.10872.

Definition code
import Definitions.Def_PricingWithTips3DM_be4ec3b9c281a1de4fd0d0b5
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Polynomial-time mux invocation expansion

This file compiles the verified fixed controller to TM2, applies the quadratic
source-length bound, and composes it with the existing list reverser to expose
the forward mux invocation stream.
-/

noncomputable section

open StateTransition

namespace CLRS.Chapter34.Turing.PolyBuilder

/-- Full builder execution through the actual halt configuration. -/
def affineMuxInvocationProgressionControllerRev_haltRun
    (segments : List AffineMuxInvocationProgression) :
    EvalsToInTime
      (step affineMuxInvocationProgressionControllerRevProgram)
      (initialCfg affineMuxInvocationProgressionControllerRevProgram
        (affineMuxInvocationProgressionFamilySourceFrames segments))
      (some (haltCfg affineMuxInvocationProgressionControllerRevProgram
        (affineMuxInvocationProgressionFamilyFrames segments).reverse))
      (affineMuxInvocationProgressionControllerFamilySteps segments + 2) := by
  have body := affineMuxInvocationProgressionControllerRev_run segments
  have haltStep : EvalsToInTime
      (step affineMuxInvocationProgressionControllerRevProgram)
      (affineMuxInvocationProgressionControllerFinishCfg
        (affineMuxInvocationProgressionFamilyFrames segments).reverse)
      (some (haltCfg affineMuxInvocationProgressionControllerRevProgram
        (affineMuxInvocationProgressionFamilyFrames segments).reverse)) 1 :=
    ⟨⟨1, rfl⟩, le_rfl⟩
  let full := EvalsToInTime.trans
    (step affineMuxInvocationProgressionControllerRevProgram)
    (affineMuxInvocationProgressionControllerFamilySteps segments + 1) 1
    _ _ _ body haltStep
  convert full using 1
  omega

/-- Compiled fixed TM2 for the reversed complete mux invocation stream. -/
noncomputable def
    affineMuxInvocationProgressionFamilyFramesRev_computableInPolyTime :
    _root_.Turing.TM2ComputableInPolyTime
      affineMuxInvocationProgressionFamilySourceFrames id
      (fun segments =>
        (affineMuxInvocationProgressionFamilyFrames segments).reverse) where
  tm := compile affineMuxInvocationProgressionControllerRevProgram
  inputAlphabet := Equiv.refl _
  outputAlphabet := Equiv.refl _
  time := 100 * Polynomial.X ^ 2 + 2
  outputsFun := fun segments => by
    have builderRun :=
      affineMuxInvocationProgressionControllerRev_haltRun segments
    have compiledRun := compile_evalsToInTime
      affineMuxInvocationProgressionControllerRevProgram builderRun
    have machineRun : _root_.StateTransition.EvalsToInTime
        (compile affineMuxInvocationProgressionControllerRevProgram).step
        (_root_.Turing.initList
          (compile affineMuxInvocationProgressionControllerRevProgram)
          (affineMuxInvocationProgressionFamilySourceFrames segments))
        (some (_root_.Turing.haltList
          (compile affineMuxInvocationProgressionControllerRevProgram)
          (affineMuxInvocationProgressionFamilyFrames segments).reverse))
        (affineMuxInvocationProgressionControllerFamilySteps segments + 2) := by
      simpa only [encodeCfg_initialCfg, encodeCfg_haltCfg] using compiledRun
    have htime :
        affineMuxInvocationProgressionControllerFamilySteps segments + 2 ≤
          (100 * Polynomial.X ^ 2 + 2).eval
            (affineMuxInvocationProgressionFamilySourceFrames segments).length := by
      have hbound :=
        affineMuxInvocationProgressionControllerFamilySteps_le segments
      simp only [Polynomial.eval_add, Polynomial.eval_mul,
        Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_ofNat]
      omega
    have boundedRun : _root_.StateTransition.EvalsToInTime
        (compile affineMuxInvocationProgressionControllerRevProgram).step
        (_root_.Turing.initList
          (compile affineMuxInvocationProgressionControllerRevProgram)
          (affineMuxInvocationProgressionFamilySourceFrames segments))
        (some (_root_.Turing.haltList
          (compile affineMuxInvocationProgressionControllerRevProgram)
          (affineMuxInvocationProgressionFamilyFrames segments).reverse))
        ((100 * Polynomial.X ^ 2 + 2).eval
          (affineMuxInvocationProgressionFamilySourceFrames segments).length) :=
      ⟨machineRun.toEvalsTo, machineRun.steps_le_m.trans htime⟩
    simpa [_root_.Turing.TM2OutputsInTime, compile] using boundedRun

/-- Forward complete mux invocation source, obtained by reversing the verified
stack-oriented controller output with the existing polynomial-time reverser.
-/
noncomputable def
    affineMuxInvocationProgressionFamilyFrames_computableInPolyTime :
    _root_.Turing.TM2ComputableInPolyTime
      affineMuxInvocationProgressionFamilySourceFrames id
      affineMuxInvocationProgressionFamilyFrames := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      affineMuxInvocationProgressionFamilyFramesRev_computableInPolyTime
      (reverse_computableInPolyTime (Γ := UnaryFrameSym))
  simpa [Function.comp_def] using Classical.choice composed

end CLRS.Chapter34.Turing.PolyBuilder
Source
https://github.com/tanktechnology/CLRS-Lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me