Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_6f927ab0586ced1c4ec7f416

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

/-!
# Certificate pair-row generator: complete run

The local row simulation is lifted to every vertex record in a canonical
certificate.  The controller then clears its persistent position counter and
halts with the exact reverse serialization of the synthetic occurrence rows.
-/

noncomputable section

open StateTransition

namespace CLRS.Chapter34.Turing.GeneralCliqueVerifier.PairGenerator

open PolyBuilder

/-- Exact scan cost for a certificate suffix whose first vertex has the given
position.  The leading one in each nonempty case consumes `vertexMark`. -/
def rowsStepsFrom : Nat → List Nat → Nat
  | _, [] => 0
  | position, vertex :: vertices =>
      1 + (2 * vertex + 5 * position + 10) +
        rowsStepsFrom (position + 1) vertices

/-- A complete certificate suffix is converted to reverse-order synthetic
occurrence rows.  The final input buffer and test bit are intentionally hidden:
they are cleared by the common terminating suffix below. -/
def rowsRun (position : Nat) (vertices : List Nat)
    (tail : List CliqueSym) (output : List UnaryFrameSym)
    (buffer : Option CliqueSym) (test : Bool) :
    Σ finalBuffer, Σ finalTest,
      EvalsToInTime (step revProgram)
        (cfg .scan buffer test
          (vertices.flatMap encodeCliqueVertex ++ tail)
          output (List.replicate position ()) [])
        (some (cfg .scan finalBuffer finalTest tail
          ((TMClique.encodeIndexedOccurrenceEntries
            (certificatePairEntriesFrom position vertices)).reverse ++ output)
          (List.replicate (position + vertices.length) ()) []))
        (rowsStepsFrom position vertices) := by
  induction vertices generalizing position output buffer test with
  | nil =>
      refine ⟨buffer, test, ?_⟩
      exact ⟨⟨0, by simp [certificatePairEntriesFrom,
        TMClique.encodeIndexedOccurrenceEntries, cfg]⟩, le_rfl⟩
  | cons vertex vertices ih =>
      let remainingInput := vertices.flatMap encodeCliqueVertex ++ tail
      have marker : EvalsToInTime (step revProgram)
          (cfg .scan buffer test
            ((vertex :: vertices).flatMap encodeCliqueVertex ++ tail)
            output (List.replicate position ()) [])
          (some (cfg .vertex (some .vertexMark) test
            ((encodeCliqueVertex vertex).tail ++ remainingInput)
            output (List.replicate position ()) [])) 1 := by
        simp only [List.flatMap_cons]
        simpa [remainingInput, encodeCliqueVertex, List.append_assoc] using
          (show EvalsToInTime (step revProgram)
              (cfg .scan buffer test
                (.vertexMark ::
                  ((encodeCliqueVertex vertex).tail ++ remainingInput))
                output (List.replicate position ()) [])
              (some (cfg .vertex (some .vertexMark) test
                ((encodeCliqueVertex vertex).tail ++ remainingInput)
                output (List.replicate position ()) [])) 1 from
            ⟨⟨1, rfl⟩, le_rfl⟩)
      have row := rowRun position vertex remainingInput output
        (some .vertexMark) test
      rcases ih (position + 1)
          ((TMClique.encodeIndexedOccurrenceEntry
            (certificatePairOccurrence position, vertex)).reverse ++ output)
          (some .recordEnd) false with
        ⟨finalBuffer, finalTest, remaining⟩
      refine ⟨finalBuffer, finalTest, ?_⟩
      let first := EvalsToInTime.trans (step revProgram)
        1 (2 * vertex + 5 * position + 10) _ _ _ marker row
      let full := EvalsToInTime.trans (step revProgram)
        _ (rowsStepsFrom (position + 1) vertices) _ _ _ first remaining
      simpa [remainingInput, rowsStepsFrom, certificatePairEntriesFrom,
        TMClique.encodeIndexedOccurrenceEntries, List.reverse_append,
        List.append_assoc, Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using
        full

private theorem clearPosition_eval (position : Nat)
    (buffer : Option CliqueSym) (test : Bool)
    (output : List UnaryFrameSym) :
    (flip Option.bind (step revProgram))^[position + 1]
      (some (cfg .clearPosition buffer test [] output
        (List.replicate position ()) [])) =
      some (cfg .clearScratch buffer false [] output [] []) := by
  induction position generalizing test with
  | zero => rfl
  | succ position ih =>
      rw [show position + 1 + 1 = (position + 1) + 1 by omega,
        Function.iterate_succ_apply]
      change
        (flip Option.bind (step revProgram))^[position + 1]
          (some (cfg .clearPosition buffer true [] output
            (List.replicate position ()) [])) = _
      exact ih true

/-- Exact full cost of the reverse-output certificate row generator. -/
def revSteps (vertices : List Nat) : Nat :=
  1 + rowsStepsFrom 0 vertices + vertices.length + 4

/-- The fixed reverse-output controller accepts the canonical certificate
encoding, clears all scratch state, and halts with exactly the required rows. -/
def revRun (vertices : List Nat) :
    EvalsToInTime (step revProgram)
      (initialCfg revProgram (encodeCliqueCertificate vertices))
      (some (haltCfg revProgram
        (TMClique.encodeIndexedOccurrenceEntries
          (certificatePairEntries vertices)).reverse))
      (revSteps vertices) := by
  have start : EvalsToInTime (step revProgram)
      (initialCfg revProgram (encodeCliqueCertificate vertices))
      (some (cfg .scan (some .certificateMark) false
        (vertices.flatMap encodeCliqueVertex) [] [] [])) 1 :=
    ⟨⟨1, rfl⟩, le_rfl⟩
  rcases rowsRun 0 vertices [] [] (some .certificateMark) false with
    ⟨finalBuffer, finalTest, rows⟩
  let reverseOutput :=
    (TMClique.encodeIndexedOccurrenceEntries
      (certificatePairEntries vertices)).reverse
  have scanEmpty : EvalsToInTime (step revProgram)
      (cfg .scan finalBuffer finalTest [] reverseOutput
        (List.replicate vertices.length ()) [])
      (some (cfg .clearPosition none finalTest [] reverseOutput
        (List.replicate vertices.length ()) [])) 1 :=
    ⟨⟨1, rfl⟩, le_rfl⟩
  have clearPosition : EvalsToInTime (step revProgram)
      (cfg .clearPosition none finalTest [] reverseOutput
        (List.replicate vertices.length ()) [])
      (some (cfg .clearScratch none false [] reverseOutput [] []))
      (vertices.length + 1) :=
    ⟨⟨vertices.length + 1,
      clearPosition_eval vertices.length none finalTest reverseOutput⟩, le_rfl⟩
  have clearScratch : EvalsToInTime (step revProgram)
      (cfg .clearScratch none false [] reverseOutput [] [])
      (some (cfg .halt none false [] reverseOutput [] [])) 1 :=
    ⟨⟨1, rfl⟩, le_rfl⟩
  have halt : EvalsToInTime (step revProgram)
      (cfg .halt none false [] reverseOutput [] [])
      (some (haltCfg revProgram reverseOutput)) 1 :=
    ⟨⟨1, rfl⟩, le_rfl⟩
  let first := EvalsToInTime.trans (step revProgram)
    1 (rowsStepsFrom 0 vertices) _ _ _ start (by
      simpa [certificatePairEntries, reverseOutput] using rows)
  let second := EvalsToInTime.trans (step revProgram)
    _ 1 _ _ _ first scanEmpty
  let third := EvalsToInTime.trans (step revProgram)
    _ (vertices.length + 1) _ _ _ second clearPosition
  let fourth := EvalsToInTime.trans (step revProgram)
    _ 1 _ _ _ third clearScratch
  let full := EvalsToInTime.trans (step revProgram)
    _ 1 _ _ _ fourth halt
  refine ⟨full.toEvalsTo, ?_⟩
  exact full.steps_le_m.trans (by
    simp [revSteps]
    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