Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorTransitionEqSource.Part3

Definition
PricingWithTips3DM_a79ce5303af3440f3d4b538fPart3

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_a79ce5303af3440f3d4b538fPart2
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

/-- The first progression coordinate is the equality carry immediately before
the segment's first public coordinate. -/
theorem transitionEqSegmentProgression_base₁
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (segment : TransitionEqSegment)
    (hwork : 0 < workHeight tm seed.height) :
    (transitionEqSegmentProgression tm seed segment).base₁ =
      transitionEqStart tm seed.height seed.start +
        6 * segment.publicBase.eval seed.height := by
  have hstart : seed.start +
      (transitionEqStartOffsetAffine tm).eval seed.height =
      transitionEqStart tm seed.height seed.start := by
    calc
      seed.start + (transitionEqStartOffsetAffine tm).eval seed.height =
          affineUnaryTripleFormValue (transitionEqStartForm tm)
            (transitionTailAffineSeed seed) := by
        symm
        exact transitionAbsoluteStartForm_value
          (transitionEqStartOffsetAffine tm) seed
      _ = transitionEqStart tm seed.height seed.start :=
        transitionEqStartForm_value tm seed hwork
  unfold transitionEqSegmentProgression transitionEqPreviousForm
  rw [transitionAbsoluteStartForm_value,
    TransitionAffineNat.eval_add, TransitionAffineNat.eval_scale]
  change seed.start +
      ((transitionEqStartOffsetAffine tm).eval seed.height +
        6 * segment.publicBase.eval seed.height) = _
  omega

/-- The second progression coordinate is the exact arithmetic final-mux wire
at the corresponding workspace segment base. -/
theorem transitionEqSegmentProgression_base₂
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (segment : TransitionEqSegment)
    (hwork : 0 < workHeight tm seed.height) :
    (transitionEqSegmentProgression tm seed segment).base₂ =
      seed.start + 2 +
          transitionDispatchListFinalMuxOffset tm seed.height
            (programLabels tm) + 3 +
        3 * segment.workspaceBase.eval seed.height := by
  unfold transitionEqSegmentProgression
  rw [transitionFinalMuxWireForm_value,
    transitionFinalMuxStartForm_value tm seed hwork]
  rfl

/-- The third progression coordinate is the exact source wire in the next
public tableau row. -/
theorem transitionEqSegmentProgression_base₃
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (segment : TransitionEqSegment) :
    (transitionEqSegmentProgression tm seed segment).base₃ =
      seed.rowBase + cfgBitCount tm seed.height +
        segment.publicBase.eval seed.height := by
  unfold transitionEqSegmentProgression transitionEqNextRowForm
    transitionTailAffineSeed affineUnaryTripleFormValue
    TransitionAffineNat.eval
  rw [← transitionCfgBitAffine_eval tm seed.height]
  unfold TransitionAffineNat.eval
  ring

/-- All three fixed strides and the runtime segment length are represented
literally in the progression descriptor. -/
theorem transitionEqSegmentProgression_steps_count
    (tm : _root_.Turing.FinTM2) (seed : TransitionRowSeed)
    (segment : TransitionEqSegment) :
    ((transitionEqSegmentProgression tm seed segment).step₁,
      (transitionEqSegmentProgression tm seed segment).step₂,
      (transitionEqSegmentProgression tm seed segment).step₃,
      (transitionEqSegmentProgression tm seed segment).count) =
      (6, 3, 1, segment.count.eval seed.height) := by
  rfl
end CLRS.Chapter34.Turing.CookLevin
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