Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_b05d2e179e08555d98d2588b

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_d43256e2a1daad1acd3ffb2a
import Definitions.Def_PricingWithTips3DM_b8c03f33e84411dcd1343113
import Definitions.Def_PricingWithTips3DM_4901b5edb9039a7b71dab674
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Formatting marked operand pairs as finite-OR frames: polynomial runtime
-/

noncomputable section

namespace CLRS.Chapter34.Turing.PolyBuilder

theorem unaryFrameMarkedOrPairFormatRevSteps_le
    (frames : List AffineOrFinPairFrame) :
    unaryFrameMarkedOrPairFormatRevSteps frames ≤
      3 * (encodeAffineOrFinMarkedPairFrames frames).length + 2 := by
  unfold unaryFrameMarkedOrPairFormatRevSteps
    encodeAffineOrFinMarkedPairFrames
  induction frames with
  | nil => simp
  | cons frame rest ih =>
      simp only [List.map_cons, List.sum_cons, List.flatMap_cons,
        List.length_append]
      have hframeLength :
          (encodeAffineOrFinMarkedPairFrame frame).length =
            frame.left + frame.right + 3 := by
        simp [encodeAffineOrFinMarkedPairFrame]
        omega
      rw [hframeLength]
      have ih' :
          (rest.map fun item =>
            2 * (item.left + item.right) + 9).sum + 2 ≤
          3 * (rest.flatMap encodeAffineOrFinMarkedPairFrame).length + 2 := by
        simpa only using ih
      omega

/-- The prepend-order formatter is a concrete linear-time TM2. -/
noncomputable def unaryFrameMarkedOrPairFormatRev_computableInPolyTime :
    _root_.Turing.TM2ComputableInPolyTime
      encodeAffineOrFinMarkedPairFrames id
      (fun frames : List AffineOrFinPairFrame =>
        (encodeAffineOrFinFrames frames).reverse) where
  tm := compile unaryFrameMarkedOrPairFormatRevProgram
  inputAlphabet := Equiv.refl _
  outputAlphabet := Equiv.refl _
  time := 3 * Polynomial.X + 2
  outputsFun := fun frames => by
    have builderRun := unaryFrameMarkedOrPairFormatRev_run frames
    have compiledRun := compile_evalsToInTime
      unaryFrameMarkedOrPairFormatRevProgram builderRun
    have machineRun : _root_.StateTransition.EvalsToInTime
        (compile unaryFrameMarkedOrPairFormatRevProgram).step
        (_root_.Turing.initList
          (compile unaryFrameMarkedOrPairFormatRevProgram)
          (encodeAffineOrFinMarkedPairFrames frames))
        (some (_root_.Turing.haltList
          (compile unaryFrameMarkedOrPairFormatRevProgram)
          (encodeAffineOrFinFrames frames).reverse))
        (unaryFrameMarkedOrPairFormatRevSteps frames) := by
      simpa only [encodeCfg_initialCfg, encodeCfg_haltCfg] using compiledRun
    have htime : unaryFrameMarkedOrPairFormatRevSteps frames ≤
        (3 * Polynomial.X + 2).eval
          (encodeAffineOrFinMarkedPairFrames frames).length := by
      simpa only [Polynomial.eval_add, Polynomial.eval_mul,
        Polynomial.eval_X, Polynomial.eval_ofNat] using
        unaryFrameMarkedOrPairFormatRevSteps_le frames
    have boundedRun : _root_.StateTransition.EvalsToInTime
        (compile unaryFrameMarkedOrPairFormatRevProgram).step
        (_root_.Turing.initList
          (compile unaryFrameMarkedOrPairFormatRevProgram)
          (encodeAffineOrFinMarkedPairFrames frames))
        (some (_root_.Turing.haltList
          (compile unaryFrameMarkedOrPairFormatRevProgram)
          (encodeAffineOrFinFrames frames).reverse))
        ((3 * Polynomial.X + 2).eval
          (encodeAffineOrFinMarkedPairFrames frames).length) :=
      ⟨machineRun.toEvalsTo, machineRun.steps_le_m.trans htime⟩
    simpa [_root_.Turing.TM2OutputsInTime, compile] using boundedRun

/-- Forward canonical finite-OR frame formatting in polynomial time. -/
noncomputable def unaryFrameMarkedOrPairFormat_computableInPolyTime :
    _root_.Turing.TM2ComputableInPolyTime
      encodeAffineOrFinMarkedPairFrames id encodeAffineOrFinFrames := by
  let composed :=
    _root_.Turing.TM2Comp.TM2ComputableInPolyTime.comp_scratch
      unaryFrameMarkedOrPairFormatRev_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