Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_b8b3022bd3ae69d159f5ef22

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_05691b74a090d581c01ca78c
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Runtime-height compact exactly-one source

One verifier stack begins with an exactly-one group of width `H + 1`.  This
module implements the fixed loaded controller for that dynamic group.  It
enters with `(H, start, rowBase)` in the three unary counters, emits the exact
compact triple, preserves `H`, advances both affine offsets, and halts at a
public continuation.
-/

noncomputable section

open StateTransition

namespace CLRS.Chapter34.Turing.PolyBuilder

/-- Finite control for one runtime-height compact frame. -/
inductive AffineExactlyOneHeightLabel
  | emitStart | saveStart | pushStartTick | pushStartSeparator
  | restoreStart | restoreStartInc
  | emitBase | saveBase | pushBaseTick | pushBaseSeparator
  | restoreBase | restoreBaseInc
  | count | saveHeight | pushCountTick
  | advanceStart₁ | advanceStart₂ | advanceStart₃ | advanceBase
  | pushExtraTick
  | advanceExtraStart₁ | advanceExtraStart₂ | advanceExtraStart₃
  | advanceExtraBase | pushCountSeparator
  | addOffset₁ | addOffset₂ | addOffset₃ | addOffset₄
  | restoreHeight | restoreHeightInc
  | finish
deriving DecidableEq, Fintype

/-- Fixed reverse-output controller for one dynamic stack-height frame. -/
def affineExactlyOneHeightRevProgram :
    Program UnaryFrameSym UnaryFrameSym where
  Label := AffineExactlyOneHeightLabel
  main := .emitStart
  op
    | .emitStart => .dec₂ .pushStartSeparator .saveStart
    | .saveStart => .pushWork₁ .tick .pushStartTick
    | .pushStartTick => .pushOutput .tick .emitStart
    | .pushStartSeparator => .pushOutput .separator .restoreStart
    | .restoreStart => .popWork₁ .emitBase fun
        | .tick => .restoreStartInc
        | _ => .emitBase
    | .restoreStartInc => .inc₂ .restoreStart
    | .emitBase => .dec₃ .pushBaseSeparator .saveBase
    | .saveBase => .pushWork₁ .tick .pushBaseTick
    | .pushBaseTick => .pushOutput .tick .emitBase
    | .pushBaseSeparator => .pushOutput .separator .restoreBase
    | .restoreBase => .popWork₁ .count fun
        | .tick => .restoreBaseInc
        | _ => .count
    | .restoreBaseInc => .inc₃ .restoreBase
    | .count => .dec₁ .pushExtraTick .saveHeight
    | .saveHeight => .pushWork₁ .tick .pushCountTick
    | .pushCountTick => .pushOutput .tick .advanceStart₁
    | .advanceStart₁ => .inc₂ .advanceStart₂
    | .advanceStart₂ => .inc₂ .advanceStart₃
    | .advanceStart₃ => .inc₂ .advanceBase
    | .advanceBase => .inc₃ .count
    | .pushExtraTick => .pushOutput .tick .advanceExtraStart₁
    | .advanceExtraStart₁ => .inc₂ .advanceExtraStart₂
    | .advanceExtraStart₂ => .inc₂ .advanceExtraStart₃
    | .advanceExtraStart₃ => .inc₂ .advanceExtraBase
    | .advanceExtraBase => .inc₃ .pushCountSeparator
    | .pushCountSeparator => .pushOutput .separator .addOffset₁
    | .addOffset₁ => .inc₂ .addOffset₂
    | .addOffset₂ => .inc₂ .addOffset₃
    | .addOffset₃ => .inc₂ .addOffset₄
    | .addOffset₄ => .inc₂ .restoreHeight
    | .restoreHeight => .popWork₁ .finish fun
        | .tick => .restoreHeightInc
        | _ => .finish
    | .restoreHeightInc => .inc₁ .restoreHeight
    | .finish => .halt

private def affineExactlyOneHeightCfg
    (label : AffineExactlyOneHeightLabel)
    (buffer₁ : Option UnaryFrameSym) (test : Bool)
    (input output work₁ : List UnaryFrameSym)
    (height start rowBase : List Unit) :
    BuilderCfg affineExactlyOneHeightRevProgram where
  label := some label
  buffer₁ := buffer₁
  buffer₂ := none
  test := test
  input := input
  output := output
  work₁ := work₁
  work₂ := []
  counter₁ := height
  counter₂ := start
  counter₃ := rowBase

/-- Public loaded entry. -/
def affineExactlyOneHeightLoadedCfg
    (height start rowBase : Nat) (input output : List UnaryFrameSym) :
    BuilderCfg affineExactlyOneHeightRevProgram :=
  affineExactlyOneHeightCfg .emitStart none false input output []
    (List.replicate height ()) (List.replicate start ())
    (List.replicate rowBase ())

/-- Public continuation after the dynamic frame. -/
def affineExactlyOneHeightFinishCfg
    (height start rowBase : Nat) (input output : List UnaryFrameSym) :
    BuilderCfg affineExactlyOneHeightRevProgram :=
  affineExactlyOneHeightCfg .finish none false input output []
    (List.replicate height ())
    (List.replicate (start + (3 * (height + 1) + 4)) ())
    (List.replicate (rowBase + (height + 1)) ())

/-- The compact frame emitted by the loaded controller. -/
def affineExactlyOneHeightFrame
    (height start rowBase : Nat) : AffineExactlyOneFrame :=
  { start := start, rowBase := rowBase, count := height + 1 }

private theorem height_replicate_append_cons {alpha : Type}
    (value : alpha) (count : Nat) (tail : List alpha) :
    List.replicate count value ++ value :: tail =
      value :: (List.replicate count value ++ tail) := by
  induction count with
  | zero => rfl
  | succ count ih =>
      simp only [List.replicate_succ, List.cons_append]
      exact congrArg (List.cons value) ih

private theorem height_emitStart_eval (value : Nat)
    (buffer₁ : Option UnaryFrameSym) (test : Bool)
    (input output work₁ : List UnaryFrameSym)
    (height rowBase : List Unit) :
    (flip Option.bind (step affineExactlyOneHeightRevProgram))^[3 * value + 1]
      (some (affineExactlyOneHeightCfg .emitStart buffer₁ test input output
        work₁ height (List.replicate value ()) rowBase)) =
      some (affineExactlyOneHeightCfg .pushStartSeparator buffer₁ false input
        (List.replicate value .tick ++ output)
        (List.replicate value .tick ++ work₁) height [] rowBase) := by
  induction value generalizing test output work₁ with
  | zero => rfl
  | succ value ih =>
      rw [show 3 * (value + 1) + 1 = (3 * value + 1) + 1 + 1 + 1 by
          omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply,
        Function.iterate_succ_apply]
      change
        (flip Option.bind (step affineExactlyOneHeightRevProgram))^[3 * value + 1]
          (some (affineExactlyOneHeightCfg .emitStart buffer₁ true input
            (.tick :: output) (.tick :: work₁) height
            (List.replicate value ()) rowBase)) = _
      simpa only [List.replicate_succ, height_replicate_append_cons,
        List.cons_append] using ih true (.tick :: output) (.tick :: work₁)

private theorem height_restoreStart_eval (value : Nat)
    (buffer₁ : Option UnaryFrameSym) (test : Bool)
    (input output : List UnaryFrameSym)
    (height current rowBase : List Unit) :
    (flip Option.bind (step affineExactlyOneHeightRevProgram))^[2 * value + 1]
      (some (affineExactlyOneHeightCfg .restoreStart buffer₁ test input
        output (List.replicate value .tick) height current rowBase)) =
      some (affineExactlyOneHeightCfg .emitBase none test input output []
        height (List.replicate value () ++ current) rowBase) := by
  induction value generalizing buffer₁ current with
  | zero => rfl
  | succ value ih =>
      rw [show 2 * (value + 1) + 1 = (2 * value + 1) + 1 + 1 by omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply]
      change
        (flip Option.bind (step affineExactlyOneHeightRevProgram))^[2 * value + 1]
          (some (affineExactlyOneHeightCfg .restoreStart (some .tick) test
            input output (List.replicate value .tick) height (() :: current)
            rowBase)) = _
      simpa only [List.replicate_succ, height_replicate_append_cons,
        List.cons_append] using ih (some .tick) (() :: current)

private theorem height_emitBase_eval (value : Nat)
    (buffer₁ : Option UnaryFrameSym) (test : Bool)
    (input output work₁ : List UnaryFrameSym)
    (height start : List Unit) :
    (flip Option.bind (step affineExactlyOneHeightRevProgram))^[3 * value + 1]
      (some (affineExactlyOneHeightCfg .emitBase buffer₁ test input output
        work₁ height start (List.replicate value ()))) =
      some (affineExactlyOneHeightCfg .pushBaseSeparator buffer₁ false input
        (List.replicate value .tick ++ output)
        (List.replicate value .tick ++ work₁) height start []) := by
  induction value generalizing test output work₁ with
  | zero => rfl
  | succ value ih =>
      rw [show 3 * (value + 1) + 1 = (3 * value + 1) + 1 + 1 + 1 by
          omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply,
        Function.iterate_succ_apply]
      change
        (flip Option.bind (step affineExactlyOneHeightRevProgram))^[3 * value + 1]
          (some (affineExactlyOneHeightCfg .emitBase buffer₁ true input
            (.tick :: output) (.tick :: work₁) height start
            (List.replicate value ()))) = _
      simpa only [List.replicate_succ, height_replicate_append_cons,
        List.cons_append] using ih true (.tick :: output) (.tick :: work₁)

private theorem height_restoreBase_eval (value : Nat)
    (buffer₁ : Option UnaryFrameSym) (test : Bool)
    (input output : List UnaryFrameSym)
    (height start current : List Unit) :
    (flip Option.bind (step affineExactlyOneHeightRevProgram))^[2 * value + 1]
      (some (affineExactlyOneHeightCfg .restoreBase buffer₁ test input output
        (List.replicate value .tick) height start current)) =
      some (affineExactlyOneHeightCfg .count none test input output [] height
        start (List.replicate value () ++ current)) := by
  induction value generalizing buffer₁ current with
  | zero => rfl
  | succ value ih =>
      rw [show 2 * (value + 1) + 1 = (2 * value + 1) + 1 + 1 by omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply]
      change
        (flip Option.bind (step affineExactlyOneHeightRevProgram))^[2 * value + 1]
          (some (affineExactlyOneHeightCfg .restoreBase (some .tick) test
            input output (List.replicate value .tick) height start
            (() :: current))) = _
      simpa only [List.replicate_succ, height_replicate_append_cons,
        List.cons_append] using ih (some .tick) (() :: current)

private theorem height_count_eval (value : Nat)
    (buffer₁ : Option UnaryFrameSym) (test : Bool)
    (input output work₁ : List UnaryFrameSym)
    (start rowBase : List Unit) :
    (flip Option.bind (step affineExactlyOneHeightRevProgram))^[7 * value + 11]
      (some (affineExactlyOneHeightCfg .count buffer₁ test input output
        work₁ (List.replicate value ()) start rowBase)) =
      some (affineExactlyOneHeightCfg .restoreHeight buffer₁ false input
        (.separator :: (List.replicate (value + 1) .tick ++ output))
        (List.replicate value .tick ++ work₁) []
        (List.replicate (3 * (value + 1) + 4) () ++ start)
        (List.replicate (value + 1) () ++ rowBase)) := by
  induction value generalizing test output work₁ start rowBase with
  | zero => rfl
  | succ value ih =>
      rw [show 7 * (value + 1) + 11 = (7 * value + 11) +
          1 + 1 + 1 + 1 + 1 + 1 + 1 by omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply,
        Function.iterate_succ_apply, Function.iterate_succ_apply,
        Function.iterate_succ_apply, Function.iterate_succ_apply,
        Function.iterate_succ_apply]
      change
        (flip Option.bind (step affineExactlyOneHeightRevProgram))^[7 * value + 11]
          (some (affineExactlyOneHeightCfg .count buffer₁ false input
            (.tick :: output) (.tick :: work₁)
            (List.replicate value ()) (() :: () :: () :: start)
            (() :: rowBase))) = _
      simpa only [List.replicate_succ, height_replicate_append_cons,
        List.cons_append,
        show 3 * (value + 1 + 1) + 4 = (3 * (value + 1) + 4) + 3 by
          omega,
        List.replicate_add, List.append_assoc] using
          ih false (.tick :: output) (.tick :: work₁)
            (() :: () :: () :: start) (() :: rowBase)

private theorem height_restoreHeight_eval (value : Nat)
    (buffer₁ : Option UnaryFrameSym) (test : Bool)
    (input output : List UnaryFrameSym)
    (current start rowBase : List Unit) :
    (flip Option.bind (step affineExactlyOneHeightRevProgram))^[2 * value + 1]
      (some (affineExactlyOneHeightCfg .restoreHeight buffer₁ test input
        output (List.replicate value .tick) current start rowBase)) =
      some (affineExactlyOneHeightCfg .finish none test input output []
        (List.replicate value () ++ current) start rowBase) := by
  induction value generalizing buffer₁ current with
  | zero => rfl
  | succ value ih =>
      rw [show 2 * (value + 1) + 1 = (2 * value + 1) + 1 + 1 by omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply]
      change
        (flip Option.bind (step affineExactlyOneHeightRevProgram))^[2 * value + 1]
          (some (affineExactlyOneHeightCfg .restoreHeight (some .tick) test
            input output (List.replicate value .tick) (() :: current) start
            rowBase)) = _
      simpa only [List.replicate_succ, height_replicate_append_cons,
        List.cons_append] using ih (some .tick) (() :: current)

/-- Exact runtime of the loaded dynamic-height component. -/
def affineExactlyOneHeightSteps (height start rowBase : Nat) : Nat :=
  5 * (start + rowBase) + 9 * height + 18

/-- The fixed component emits the exact compact height frame, preserves the
height counter, and reaches its public continuation in the stated time. -/
def affineExactlyOneHeight_runToFinish
    (height start rowBase : Nat) (input output : List UnaryFrameSym) :
    EvalsToInTime (step affineExactlyOneHeightRevProgram)
      (affineExactlyOneHeightLoadedCfg height start rowBase input output)
      (some (affineExactlyOneHeightFinishCfg height start rowBase input
        ((encodeAffineExactlyOneCompactFrame
          (affineExactlyOneHeightFrame height start rowBase)).reverse ++
          output)))
      (affineExactlyOneHeightSteps height start rowBase) := by
  let afterStart := affineExactlyOneHeightCfg .pushStartSeparator none false
    input (List.replicate start .tick ++ output)
    (List.replicate start .tick) (List.replicate height ()) []
    (List.replicate rowBase ())
  let beforeRestoreStart := affineExactlyOneHeightCfg .restoreStart none false
    input (.separator :: (List.replicate start .tick ++ output))
    (List.replicate start .tick) (List.replicate height ()) []
    (List.replicate rowBase ())
  let beforeBase := affineExactlyOneHeightCfg .emitBase none false input
    (.separator :: (List.replicate start .tick ++ output)) []
    (List.replicate height ()) (List.replicate start ())
    (List.replicate rowBase ())
  let afterBase := affineExactlyOneHeightCfg .pushBaseSeparator none false input
    (List.replicate rowBase .tick ++
      .separator :: (List.replicate start .tick ++ output))
    (List.replicate rowBase .tick) (List.replicate height ())
    (List.replicate start ()) []
  let beforeRestoreBase := affineExactlyOneHeightCfg .restoreBase none false
    input
    (.separator :: (List.replicate rowBase .tick ++
      .separator :: (List.replicate start .tick ++ output)))
    (List.replicate rowBase .tick) (List.replicate height ())
    (List.replicate start ()) []
  let beforeCount := affineExactlyOneHeightCfg .count none false input
    (.separator :: (List.replicate rowBase .tick ++
      .separator :: (List.replicate start .tick ++ output))) []
    (List.replicate height ()) (List.replicate start ())
    (List.replicate rowBase ())
  let beforeRestoreHeight := affineExactlyOneHeightCfg .restoreHeight none false
    input
    (.separator :: (List.replicate (height + 1) .tick ++
      .separator :: (List.replicate rowBase .tick ++
        .separator :: (List.replicate start .tick ++ output))))
    (List.replicate height .tick) []
    (List.replicate (start + (3 * (height + 1) + 4)) ())
    (List.replicate (rowBase + (height + 1)) ())
  have hstart : EvalsToInTime (step affineExactlyOneHeightRevProgram)
      (affineExactlyOneHeightLoadedCfg height start rowBase input output)
      (some afterStart) (3 * start + 1) := by
    refine ⟨⟨3 * start + 1, ?_⟩, le_rfl⟩
    simpa [affineExactlyOneHeightLoadedCfg, afterStart] using
      height_emitStart_eval start none false input output []
        (List.replicate height ()) (List.replicate rowBase ())
  have hstartSep : EvalsToInTime (step affineExactlyOneHeightRevProgram)
      afterStart (some beforeRestoreStart) 1 := ⟨⟨1, rfl⟩, le_rfl⟩
  have hrestoreStart : EvalsToInTime
      (step affineExactlyOneHeightRevProgram) beforeRestoreStart
      (some beforeBase) (2 * start + 1) := by
    refine ⟨⟨2 * start + 1, ?_⟩, le_rfl⟩
    simpa [beforeRestoreStart, beforeBase] using
      height_restoreStart_eval start none false input
        (.separator :: (List.replicate start .tick ++ output))
        (List.replicate height ()) [] (List.replicate rowBase ())
  have hbase : EvalsToInTime (step affineExactlyOneHeightRevProgram)
      beforeBase (some afterBase) (3 * rowBase + 1) := by
    refine ⟨⟨3 * rowBase + 1, ?_⟩, le_rfl⟩
    simpa [beforeBase, afterBase] using
      height_emitBase_eval rowBase none false input
        (.separator :: (List.replicate start .tick ++ output)) []
        (List.replicate height ()) (List.replicate start ())
  have hbaseSep : EvalsToInTime (step affineExactlyOneHeightRevProgram)
      afterBase (some beforeRestoreBase) 1 := ⟨⟨1, rfl⟩, le_rfl⟩
  have hrestoreBase : EvalsToInTime
      (step affineExactlyOneHeightRevProgram) beforeRestoreBase
      (some beforeCount) (2 * rowBase + 1) := by
    refine ⟨⟨2 * rowBase + 1, ?_⟩, le_rfl⟩
    simpa [beforeRestoreBase, beforeCount] using
      height_restoreBase_eval rowBase none false input
        (.separator :: (List.replicate rowBase .tick ++
          .separator :: (List.replicate start .tick ++ output)))
        (List.replicate height ()) (List.replicate start ()) []
  have hcount : EvalsToInTime (step affineExactlyOneHeightRevProgram)
      beforeCount (some beforeRestoreHeight) (7 * height + 11) := by
    refine ⟨⟨7 * height + 11, ?_⟩, le_rfl⟩
    simpa [beforeCount, beforeRestoreHeight,
      List.replicate_append_replicate, Nat.add_assoc, Nat.add_comm,
      Nat.add_left_comm] using
      height_count_eval height none false input
        (.separator :: (List.replicate rowBase .tick ++
          .separator :: (List.replicate start .tick ++ output))) []
        (List.replicate start ()) (List.replicate rowBase ())
  have hrestoreHeight : EvalsToInTime
      (step affineExactlyOneHeightRevProgram) beforeRestoreHeight
      (some (affineExactlyOneHeightFinishCfg height start rowBase input
        (.separator :: (List.replicate (height + 1) .tick ++
          .separator :: (List.replicate rowBase .tick ++
            .separator :: (List.replicate start .tick ++ output))))))
      (2 * height + 1) := by
    refine ⟨⟨2 * height + 1, ?_⟩, le_rfl⟩
    simpa [beforeRestoreHeight, affineExactlyOneHeightFinishCfg] using
      height_restoreHeight_eval height none false input
        (.separator :: (List.replicate (height + 1) .tick ++
          .separator :: (List.replicate rowBase .tick ++
            .separator :: (List.replicate start .tick ++ output)))) []
        (List.replicate (start + (3 * (height + 1) + 4)) ())
        (List.replicate (rowBase + (height + 1)) ())
  let h₁ := EvalsToInTime.trans (step affineExactlyOneHeightRevProgram)
    _ 1 _ afterStart _ hstart hstartSep
  let h₂ := EvalsToInTime.trans (step affineExactlyOneHeightRevProgram)
    _ _ _ beforeRestoreStart _ h₁ hrestoreStart
  let h₃ := EvalsToInTime.trans (step affineExactlyOneHeightRevProgram)
    _ _ _ beforeBase _ h₂ hbase
  let h₄ := EvalsToInTime.trans (step affineExactlyOneHeightRevProgram)
    _ 1 _ afterBase _ h₃ hbaseSep
  let h₅ := EvalsToInTime.trans (step affineExactlyOneHeightRevProgram)
    _ _ _ beforeRestoreBase _ h₄ hrestoreBase
  let h₆ := EvalsToInTime.trans (step affineExactlyOneHeightRevProgram)
    _ _ _ beforeCount _ h₅ hcount
  let full := EvalsToInTime.trans (step affineExactlyOneHeightRevProgram)
    _ _ _ beforeRestoreHeight _ h₆ hrestoreHeight
  convert full using 1
  · simp [affineExactlyOneHeightFrame, encodeAffineExactlyOneCompactFrame,
      encodeUnaryFrame, encodeUnaryFrameBlock, List.reverse_append,
      List.append_assoc]
  · simp [affineExactlyOneHeightSteps]
    omega

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