Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralClique.VerifierMachine.PairGenerator.Simulation

Definition
PricingWithTips3DM_2b183c60fe1ccf49ea00d2fc

by qmaai2907271020 · Oct 23, 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_6faa19b900f252906e4cf1c8
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Certificate pair-row generator: one-row simulation
-/

noncomputable section

open StateTransition

namespace CLRS.Chapter34.Turing.GeneralCliqueVerifier.PairGenerator

open PolyBuilder

private theorem 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 prependCliqueTicks_eq_replicate (count : Nat)
    (tail : List CliqueSym) :
    prependCliqueTicks count tail = List.replicate count .tick ++ tail := by
  induction count with
  | zero => rfl
  | succ count ih =>
      simp [prependCliqueTicks, List.replicate_succ, ih]

private theorem readVertex_eval (vertex : Nat)
    (buffer : Option CliqueSym) (test : Bool)
    (tail : List CliqueSym) (output : List UnaryFrameSym)
    (position scratch : Nat) :
    (flip Option.bind (step revProgram))^[2 * vertex + 1]
      (some (cfg .vertex buffer test
        (List.replicate vertex CliqueSym.tick ++
          CliqueSym.recordEnd :: tail)
        output (List.replicate position ())
        (List.replicate scratch ()))) =
      some (cfg .pushVertexSeparator (some .recordEnd) test tail
        (List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate position ()) (List.replicate scratch ())) := by
  induction vertex generalizing buffer output with
  | zero => rfl
  | succ vertex ih =>
      rw [show 2 * (vertex + 1) + 1 = (2 * vertex + 1) + 1 + 1 by
          omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply]
      change
        (flip Option.bind (step revProgram))^[2 * vertex + 1]
          (some (cfg .vertex (some .tick) test
            (List.replicate vertex CliqueSym.tick ++
              CliqueSym.recordEnd :: tail)
            (.tick :: output) (List.replicate position ())
            (List.replicate scratch ()))) = _
      simpa [List.replicate_succ, replicate_append_cons] using
        ih (some .tick) (.tick :: output)

private theorem copyPosition_eval (position saved : Nat)
    (buffer : Option CliqueSym) (test : Bool)
    (input : List CliqueSym) (output : List UnaryFrameSym) :
    (flip Option.bind (step revProgram))^[3 * position + 1]
      (some (cfg .copyPosition buffer test input output
        (List.replicate position ()) (List.replicate saved ()))) =
      some (cfg .pushPositionSeparator buffer false input
        (List.replicate position UnaryFrameSym.tick ++ output) []
        (List.replicate (saved + position) ())) := by
  induction position generalizing saved test output with
  | zero => rfl
  | succ position ih =>
      rw [show 3 * (position + 1) + 1 =
          (3 * position + 1) + 1 + 1 + 1 by omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply,
        Function.iterate_succ_apply]
      change
        (flip Option.bind (step revProgram))^[3 * position + 1]
          (some (cfg .copyPosition buffer true input (.tick :: output)
            (List.replicate position ())
            (List.replicate (saved + 1) ()))) = _
      simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm,
        List.replicate_succ, replicate_append_cons] using
        ih (saved + 1) true (.tick :: output)

private theorem restorePosition_eval (saved restored : Nat)
    (buffer : Option CliqueSym) (test : Bool)
    (input : List CliqueSym) (output : List UnaryFrameSym) :
    (flip Option.bind (step revProgram))^[2 * saved + 1]
      (some (cfg .restorePosition buffer test input output
        (List.replicate restored ()) (List.replicate saved ()))) =
      some (cfg .pushPolaritySeparator buffer false input output
        (List.replicate (restored + saved) ()) []) := by
  induction saved generalizing restored test with
  | zero => rfl
  | succ saved ih =>
      rw [show 2 * (saved + 1) + 1 =
          (2 * saved + 1) + 1 + 1 by omega,
        Function.iterate_succ_apply, Function.iterate_succ_apply]
      change
        (flip Option.bind (step revProgram))^[2 * saved + 1]
          (some (cfg .restorePosition buffer true input output
            (List.replicate (restored + 1) ())
            (List.replicate saved ()))) = _
      simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using
        ih (restored + 1) true

/-- Exact run for one canonical certificate vertex, returning to the clean
row boundary with the position counter advanced once. -/
def rowRun (position vertex : Nat) (tail : List CliqueSym)
    (output : List UnaryFrameSym) (buffer : Option CliqueSym)
    (test : Bool) :
    EvalsToInTime (step revProgram)
      (cfg .vertex buffer test
        ((encodeCliqueVertex vertex).tail ++ tail)
        output (List.replicate position ()) [])
      (some (cfg .scan (some .recordEnd) false tail
        ((TMClique.encodeIndexedOccurrenceEntry
          (certificatePairOccurrence position, vertex)).reverse ++ output)
        (List.replicate (position + 1) ()) []))
      (2 * vertex + 5 * position + 10) := by
  have read : EvalsToInTime (step revProgram)
      (cfg .vertex buffer test
        ((encodeCliqueVertex vertex).tail ++ tail)
        output (List.replicate position ()) [])
      (some (cfg .pushVertexSeparator (some .recordEnd) test tail
        (List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate position ()) []))
      (2 * vertex + 1) :=
    ⟨⟨2 * vertex + 1, by
      simpa [encodeCliqueVertex, prependCliqueTicks_eq_replicate] using
        readVertex_eval vertex buffer test tail output position 0⟩, le_rfl⟩
  have vertexSeparator : EvalsToInTime (step revProgram)
      (cfg .pushVertexSeparator (some .recordEnd) test tail
        (List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate position ()) [])
      (some (cfg .copyPosition (some .recordEnd) test tail
        (.separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate position ()) [])) 1 :=
    ⟨⟨1, rfl⟩, le_rfl⟩
  have copy : EvalsToInTime (step revProgram)
      (cfg .copyPosition (some .recordEnd) test tail
        (.separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate position ()) [])
      (some (cfg .pushPositionSeparator (some .recordEnd) false tail
        (List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        [] (List.replicate position ())))
      (3 * position + 1) :=
    ⟨⟨3 * position + 1, by
      simpa [List.append_assoc] using copyPosition_eval position 0
        (some .recordEnd) test tail
        (.separator :: List.replicate vertex UnaryFrameSym.tick ++ output)⟩,
      le_rfl⟩
  have positionSeparator : EvalsToInTime (step revProgram)
      (cfg .pushPositionSeparator (some .recordEnd) false tail
        (List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        [] (List.replicate position ()))
      (some (cfg .restorePosition (some .recordEnd) false tail
        (.separator :: List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        [] (List.replicate position ()))) 1 :=
    ⟨⟨1, rfl⟩, le_rfl⟩
  have restore : EvalsToInTime (step revProgram)
      (cfg .restorePosition (some .recordEnd) false tail
        (.separator :: List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        [] (List.replicate position ()))
      (some (cfg .pushPolaritySeparator (some .recordEnd) false tail
        (.separator :: List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate position ()) []))
      (2 * position + 1) :=
    ⟨⟨2 * position + 1, by
      simpa using restorePosition_eval position 0 (some .recordEnd) false tail
        (.separator :: List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)⟩,
      le_rfl⟩
  let afterPolarity := cfg .pushVariableTick (some .recordEnd) false tail
    (.separator :: .separator ::
      List.replicate position UnaryFrameSym.tick ++
      .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
    (List.replicate position ()) []
  let afterVariableTick := cfg .pushVariableSeparator (some .recordEnd) false
    tail (.tick :: .separator :: .separator ::
      List.replicate position UnaryFrameSym.tick ++
      .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
    (List.replicate position ()) []
  let afterVariableSeparator := cfg .pushRowEnd (some .recordEnd) false tail
    (.separator :: .tick :: .separator :: .separator ::
      List.replicate position UnaryFrameSym.tick ++
      .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
    (List.replicate position ()) []
  let afterRowEnd := cfg .advancePosition (some .recordEnd) false tail
    (.frameEnd :: .separator :: .tick :: .separator :: .separator ::
      List.replicate position UnaryFrameSym.tick ++
      .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
    (List.replicate position ()) []
  have finish : EvalsToInTime (step revProgram)
      (cfg .pushPolaritySeparator (some .recordEnd) false tail
        (.separator :: List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate position ()) [])
      (some (cfg .scan (some .recordEnd) false tail
        (.frameEnd :: .separator :: .tick :: .separator :: .separator ::
          List.replicate position UnaryFrameSym.tick ++
          .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
        (List.replicate (position + 1) ()) [])) 5 := by
    have pushPolarity : EvalsToInTime (step revProgram)
        (cfg .pushPolaritySeparator (some .recordEnd) false tail
          (.separator :: List.replicate position UnaryFrameSym.tick ++
            .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
          (List.replicate position ()) [])
        (some afterPolarity) 1 :=
      ⟨⟨1, rfl⟩, le_rfl⟩
    have pushVariable : EvalsToInTime (step revProgram)
        afterPolarity (some afterVariableTick) 1 :=
      ⟨⟨1, rfl⟩, le_rfl⟩
    have pushVariableSeparator : EvalsToInTime (step revProgram)
        afterVariableTick (some afterVariableSeparator) 1 :=
      ⟨⟨1, rfl⟩, le_rfl⟩
    have pushEnd : EvalsToInTime (step revProgram)
        afterVariableSeparator (some afterRowEnd) 1 :=
      ⟨⟨1, rfl⟩, le_rfl⟩
    have advance : EvalsToInTime (step revProgram)
        afterRowEnd
        (some (cfg .scan (some .recordEnd) false tail
          (.frameEnd :: .separator :: .tick :: .separator :: .separator ::
            List.replicate position UnaryFrameSym.tick ++
            .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
          (List.replicate (position + 1) ()) [])) 1 := by
      simpa [afterRowEnd, List.replicate_succ] using
        (show EvalsToInTime (step revProgram) afterRowEnd
            (some (cfg .scan (some .recordEnd) false tail
              (.frameEnd :: .separator :: .tick :: .separator :: .separator ::
                List.replicate position UnaryFrameSym.tick ++
                .separator :: List.replicate vertex UnaryFrameSym.tick ++ output)
              (() :: List.replicate position ()) [])) 1 from
          ⟨⟨1, rfl⟩, le_rfl⟩)
    let firstFinish := EvalsToInTime.trans (step revProgram)
      1 1 _ _ _ pushPolarity pushVariable
    let secondFinish := EvalsToInTime.trans (step revProgram)
      _ 1 _ _ _ firstFinish pushVariableSeparator
    let thirdFinish := EvalsToInTime.trans (step revProgram)
      _ 1 _ _ _ secondFinish pushEnd
    let fullFinish := EvalsToInTime.trans (step revProgram)
      _ 1 _ _ _ thirdFinish advance
    exact fullFinish
  let first := EvalsToInTime.trans (step revProgram)
    (2 * vertex + 1) 1 _ _ _ read vertexSeparator
  let second := EvalsToInTime.trans (step revProgram)
    _ (3 * position + 1) _ _ _ first copy
  let third := EvalsToInTime.trans (step revProgram)
    _ 1 _ _ _ second positionSeparator
  let fourth := EvalsToInTime.trans (step revProgram)
    _ (2 * position + 1) _ _ _ third restore
  let full := EvalsToInTime.trans (step revProgram) _ 5 _ _ _ fourth finish
  convert full using 1 <;>
    simp [encode_certificatePairEntry, encodeUnaryFrame,
      encodeUnaryFrameBlock, List.replicate_succ, Nat.add_assoc,
      Nat.add_comm, Nat.add_left_comm]
  omega

end CLRS.Chapter34.Turing.GeneralCliqueVerifier.PairGenerator
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