Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.Dev.B10_Parse

Definition
PricingWithTips3DM_672801362a1c7ec753878344

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

/-!
# Dev B10: the recursive descent (`parse_phase`)

The `parse_phase` run lemma: the recursive descent that reads `inp`, emits the reversed Tseitin clauses, pushes the value variable, and reaches `reduce`.
-/

namespace CLRS

namespace Chapter34

open CLRS.Chapter34
open Computability StateTransition
open Turing

namespace Turing

namespace TM3CNF

-- ============================================================
-- parse: the recursive descent (`parse_phase`)
--
-- The `parse_phase` lemma is the run lemma for the recursive descent.  For any
-- input `inp`, `decodeAux inp.length inp` extracts the first formula `f` and
-- the continuation `rest`; the machine reads `inp` from `rd`, emits the
-- reversed Tseitin clauses of `f` onto `o`, pushes `f`'s value variable onto
-- `val`, advances the counter past the auxiliary variables allocated for `f`,
-- and reaches `reduce` with the continuation `rest` on `in`.  Malformed input
-- (end of input, stray `endMark`, or a `varMark` with no index run) yields
-- `const false`, which the junk `const false` phases handle.
-- ============================================================

/-- Count the leading `endMark`s of a list, returning the count and the
suffix. -/
def endMarkRun : List FormulaSym → Nat × List FormulaSym
  | FormulaSym.endMark :: rest =>
      let (i, suf) := endMarkRun rest
      (i + 1, suf)
  | rest => (0, rest)

/-- `endMarkRun` splits a list at the first non-`endMark`. -/
lemma endMarkRun_spec (rest : List FormulaSym) :
    let (i, suf) := endMarkRun rest
    rest = List.replicate i FormulaSym.endMark ++ suf ∧ suf.head? ≠ some FormulaSym.endMark := by
  induction rest with
  | nil => simp [endMarkRun]
  | cons s rest' ih =>
      cases s with
      | endMark =>
          cases h : endMarkRun rest' with
          | mk i suf =>
              have hrest : rest' = List.replicate i FormulaSym.endMark ++ suf := by
                simpa [h] using ih.1
              have hsuf : suf.head? ≠ some FormulaSym.endMark := by
                simpa [h] using ih.2
              have hrun : endMarkRun (FormulaSym.endMark :: rest') = (i + 1, suf) := by
                rw [endMarkRun, h]
              rw [hrun]
              constructor
              · rw [hrest]
                rw [show FormulaSym.endMark :: (List.replicate i FormulaSym.endMark ++ suf) =
                    List.replicate (i + 1) FormulaSym.endMark ++ suf by
                      rw [show i + 1 = Nat.succ i by omega]
                      simp [List.replicate_succ, List.cons_append]]
              · simpa using hsuf
      | _ => simp [endMarkRun]

/-- `decodeVar` of a run of `k ≥ 1` `endMark`s yields the variable `k - 1`,
leaving the suffix untouched. -/
lemma decodeVar_endMarkRun (rest : List FormulaSym) (k : Nat) (suf : List FormulaSym)
    (hk : 1 ≤ k) (h : endMarkRun rest = (k, suf)) :
    decodeVar rest = (Formula.var (k - 1), suf) := by
  have hspec := endMarkRun_spec rest
  rw [h] at hspec
  have hrest : rest = List.replicate k FormulaSym.endMark ++ suf := by
    simpa using hspec.1
  have hsuf : ValidSuffix suf := by
    simpa [ValidSuffix] using hspec.2
  rw [hrest]
  have hk : k = (k - 1) + 1 := by omega
  rw [hk]
  exact decodeVar_enc (k - 1) hsuf

/-- A `var` decode means the input had a full unary index run: `decodeVar l =
(var i, rest)` implies `l` is `varEnc i` followed by a valid continuation. -/
lemma decodeVar_eq_var (l : List FormulaSym) (i : Nat) (rest : List FormulaSym)
    (h : decodeVar l = (Formula.var i, rest)) :
    l = List.replicate (i + 1) FormulaSym.endMark ++ rest ∧ rest.head? ≠ some FormulaSym.endMark := by
  have hl : l.head? = some FormulaSym.endMark := by
    by_contra hne
    cases l with
    | nil => simp [decodeVar] at h
    | cons s l' =>
        have hs : s ≠ FormulaSym.endMark := by
          intro hse
          apply hne
          simp [hse]
        simp [decodeVar, hs] at h
  cases hk : endMarkRun l with
  | mk k suf =>
      have hspec := endMarkRun_spec l
      rw [hk] at hspec
      have hk1 : 1 ≤ k := by
        by_contra hk0
        have hk0' : k = 0 := by omega
        rw [hk0'] at hspec
        have hsame : l = suf := by simpa using hspec.1
        have hne' : l.head? ≠ some FormulaSym.endMark := by
          rw [hsame]
          exact hspec.2
        exact hne' hl
      have hdec := decodeVar_endMarkRun l k suf hk1 hk
      rw [hdec] at h
      have hk' : k - 1 = i := by
        simpa using congrArg Prod.fst h
      have hsuf : suf = rest := congrArg Prod.snd h
      constructor
      · rw [hspec.1]
        rw [hsuf]
        rw [show k = i + 1 by omega]
      · rw [← hsuf]
        exact hspec.2

/-- The number of steps the machine takes to parse a formula `f` starting from
auxiliary index `c` (matching the phase lemma step counts). -/
def parseSteps : Formula → Nat → Nat
  | Formula.var i, c => i + 3
  | Formula.const b, c => if b then 2 * c + 4 else 2 * c + 5
  | Formula.not f, c =>
      let (_, y₁, c₁) := to3CNF' f c
      2 + parseSteps f c + (4 * c₁ + 3 * y₁ + 16)
  | Formula.and f g, c =>
      let (_, y₁, c₁) := to3CNF' f c
      let (_, y₂, c₂) := to3CNF' g c₁
      3 + parseSteps f c + parseSteps g c₁ + (6 * c₂ + 3 * y₁ + 7 * y₂ + 44)
  | Formula.or f g, c =>
      let (_, y₁, c₁) := to3CNF' f c
      let (_, y₂, c₂) := to3CNF' g c₁
      3 + parseSteps f c + parseSteps g c₁ + (6 * c₂ + 3 * y₁ + 7 * y₂ + 44)
  | Formula.iff f g, c =>
      let (_, y₁, c₁) := to3CNF' f c
      let (_, y₂, c₂) := to3CNF' g c₁
      3 + parseSteps f c + parseSteps g c₁ + (8 * c₂ + 7 * y₁ + 15 * y₂ + 86)

/-- `decodeVarIdx` leaves a suffix no longer than its input. -/
lemma decodeVarIdx_suffix_le (i : Nat) (l : List FormulaSym) :
    (decodeVarIdx i l).2.length ≤ l.length := by
  induction l generalizing i with
  | nil => simp [decodeVarIdx]
  | cons s l' ih =>
      cases s with
      | endMark =>
          have h := ih (i + 1)
          simp [decodeVarIdx, List.length_cons]
          omega
      | _ => simp [decodeVarIdx]

/-- `decodeVar` leaves a suffix no longer than its input. -/
lemma decodeVar_suffix_le (l : List FormulaSym) :
    (decodeVar l).2.length ≤ l.length := by
  cases l with
  | nil => simp [decodeVar]
  | cons s l' =>
      cases s with
      | endMark =>
          have h := decodeVarIdx_suffix_le 0 l'
          simp [decodeVar, List.length_cons]
          omega
      | _ => simp [decodeVar]

lemma decodeAux_lit (b : Bool) (n : Nat) (l : List FormulaSym) :
    decodeAux (Nat.succ n) (FormulaSym.lit b :: l) = (Formula.const b, l) := by
  simp [decodeAux]

/-- `decodeAux` on the empty list is the junk `const false`. -/
lemma decodeAux_nil (b : Nat) :
    decodeAux b [] = (Formula.const false, []) := by
  cases b <;> simp [decodeAux]


/-- `decodeAux` on a `varMark` routes to `decodeVar`. -/
lemma decodeAux_varMark (n : Nat) (l : List FormulaSym) :
    decodeAux (Nat.succ n) (FormulaSym.varMark :: l) = decodeVar l := by
  simp [decodeAux]

/-- `decodeAux` on a stray `endMark` is the junk `const false`. -/
lemma decodeAux_endMark (n : Nat) (l : List FormulaSym) :
    decodeAux (Nat.succ n) (FormulaSym.endMark :: l) = (Formula.const false, l) := by
  simp [decodeAux]

/-- `decodeAux` on a `notMark` recurses with one less budget. -/
lemma decodeAux_notMark (n : Nat) (l : List FormulaSym) :
    decodeAux (Nat.succ n) (FormulaSym.notMark :: l) =
      (Formula.not (decodeAux n l).1, (decodeAux n l).2) := by
  simp [decodeAux]

/-- `decodeAux` on an `andMark` recurses with one less budget on both children. -/
lemma decodeAux_andMark (n : Nat) (l : List FormulaSym) :
    decodeAux (Nat.succ n) (FormulaSym.andMark :: l) =
      (Formula.and (decodeAux n l).1 (decodeAux n (decodeAux n l).2).1,
       (decodeAux n (decodeAux n l).2).2) := by
  simp [decodeAux]

/-- `decodeAux` on an `orMark` recurses with one less budget on both children. -/
lemma decodeAux_orMark (n : Nat) (l : List FormulaSym) :
    decodeAux (Nat.succ n) (FormulaSym.orMark :: l) =
      (Formula.or (decodeAux n l).1 (decodeAux n (decodeAux n l).2).1,
       (decodeAux n (decodeAux n l).2).2) := by
  simp [decodeAux]

/-- `decodeAux` on an `iffMark` recurses with one less budget on both children. -/
lemma decodeAux_iffMark (n : Nat) (l : List FormulaSym) :
    decodeAux (Nat.succ n) (FormulaSym.iffMark :: l) =
      (Formula.iff (decodeAux n l).1 (decodeAux n (decodeAux n l).2).1,
       (decodeAux n (decodeAux n l).2).2) := by
  simp [decodeAux]

/-- A non-empty input with a sufficient budget has `1 ≤ b`. -/
lemma budget_pos_of_cons (s : FormulaSym) (l : List FormulaSym) (b : Nat)
    (h : (s :: l).length ≤ b) : 1 ≤ b := by
  simp [List.length_cons] at h
  omega

/-- `decodeVarIdx` always yields a variable: it only ever counts `endMark`s. -/
lemma decodeVarIdx_is_var (i : Nat) (l : List FormulaSym) :
    ∃ k, (decodeVarIdx i l).1 = Formula.var k := by
  induction l generalizing i with
  | nil => refine ⟨i, ?_⟩; simp [decodeVarIdx]
  | cons s l' ih =>
      cases s with
      | endMark =>
          rcases ih (i + 1) with ⟨k, hk⟩
          refine ⟨k, ?_⟩
          simp [decodeVarIdx] at hk ⊢
          exact hk
      | _ =>
          refine ⟨i, ?_⟩
          simp [decodeVarIdx]

/-- `decodeVar` never yields a `not` formula (only variables or the junk
`const false`). -/
lemma decodeVar_fst_ne_not (l : List FormulaSym) (f' : Formula) :
    (decodeVar l).1 ≠ Formula.not f' := by
  cases l with
  | nil => simp [decodeVar]
  | cons s l' =>
      cases s with
      | endMark =>
          rw [show decodeVar (FormulaSym.endMark :: l') = decodeVarIdx 0 l' by rfl]
          rcases decodeVarIdx_is_var 0 l' with ⟨k, hk⟩
          rw [hk]
          simp
      | _ => simp [decodeVar]

/-- `decodeVar` never yields `const true`. -/
lemma decodeVar_fst_ne_const_true (l : List FormulaSym) :
    (decodeVar l).1 ≠ Formula.const true := by
  cases l with
  | nil => simp [decodeVar]
  | cons s l' =>
      cases s with
      | endMark =>
          rw [show decodeVar (FormulaSym.endMark :: l') = decodeVarIdx 0 l' by rfl]
          rcases decodeVarIdx_is_var 0 l' with ⟨k, hk⟩
          rw [hk]
          simp
      | _ => simp [decodeVar]

/-- `decodeVar` never yields an `and`. -/
lemma decodeVar_fst_ne_and (l : List FormulaSym) (f' g' : Formula) :
    (decodeVar l).1 ≠ Formula.and f' g' := by
  cases l with
  | nil => simp [decodeVar]
  | cons s l' =>
      cases s with
      | endMark =>
          rw [show decodeVar (FormulaSym.endMark :: l') = decodeVarIdx 0 l' by rfl]
          rcases decodeVarIdx_is_var 0 l' with ⟨k, hk⟩
          rw [hk]
          simp
      | _ => simp [decodeVar]

/-- `decodeVar` never yields an `or`. -/
lemma decodeVar_fst_ne_or (l : List FormulaSym) (f' g' : Formula) :
    (decodeVar l).1 ≠ Formula.or f' g' := by
  cases l with
  | nil => simp [decodeVar]
  | cons s l' =>
      cases s with
      | endMark =>
          rw [show decodeVar (FormulaSym.endMark :: l') = decodeVarIdx 0 l' by rfl]
          rcases decodeVarIdx_is_var 0 l' with ⟨k, hk⟩
          rw [hk]
          simp
      | _ => simp [decodeVar]

/-- `decodeVar` never yields an `iff`. -/
lemma decodeVar_fst_ne_iff (l : List FormulaSym) (f' g' : Formula) :
    (decodeVar l).1 ≠ Formula.iff f' g' := by
  cases l with
  | nil => simp [decodeVar]
  | cons s l' =>
      cases s with
      | endMark =>
          rw [show decodeVar (FormulaSym.endMark :: l') = decodeVarIdx 0 l' by rfl]
          rcases decodeVarIdx_is_var 0 l' with ⟨k, hk⟩
          rw [hk]
          simp
      | _ => simp [decodeVar]

/-- Compose two machine segments: `^[n₁] A = B` and `^[n₂] B = C` give
`^[n₂ + n₁] A = C`. -/
lemma step_comp {A B C : Option (mach).Cfg} (n₁ n₂ : Nat)
    (h₁ : (flip bind Sstep)^[n₁] A = B) (h₂ : (flip bind Sstep)^[n₂] B = C) :
    (flip bind Sstep)^[n₂ + n₁] A = C := by
  rw [Function.iterate_add_apply]
  rw [h₁]
  rw [h₂]

/-- Three-step composition. -/
lemma step_comp3 {A B C D : Option (mach).Cfg} (n₁ n₂ n₃ : Nat)
    (h₁ : (flip bind Sstep)^[n₁] A = B) (h₂ : (flip bind Sstep)^[n₂] B = C)
    (h₃ : (flip bind Sstep)^[n₃] C = D) :
    (flip bind Sstep)^[n₃ + (n₂ + n₁)] A = D := by
  rw [Function.iterate_add_apply]
  rw [step_comp n₁ n₂ h₁ h₂]
  rw [h₃]

/-- Compose a single step followed by `n₂` steps. -/
lemma step_comp_single {A : Option (mach).Cfg} {B C : (mach).Cfg} (n₂ : Nat)
    (h₁ : Sstep B = some C) (h₂ : (flip bind Sstep)^[n₂] (some C) = A) :
    (flip bind Sstep)^[n₂ + 1] (some B) = A := by
  rw [Function.iterate_add_apply]
  rw [show (flip bind Sstep)^[1] (some B) = Sstep B by simp [flip]]
  rw [h₁]
  exact h₂

/-- Compose `n₁` steps followed by a single step. -/
lemma step_single_comp {A C : Option (mach).Cfg} {B : (mach).Cfg} (n₁ : Nat)
    (h₁ : (flip bind Sstep)^[n₁] A = some B) (h₂ : Sstep B = some C) :
    (flip bind Sstep)^[1 + n₁] A = some C := by
  rw [show 1 + n₁ = Nat.succ n₁ by omega]
  rw [Function.iterate_succ_apply']
  rw [h₁]
  change Sstep B = some C
  exact h₂

/-- `decodeAux` never lengthens the continuation. -/
lemma decodeAux_suffix_le (n : Nat) (l : List FormulaSym) :
    (decodeAux n l).2.length ≤ l.length := by
  revert n
  let P : List FormulaSym → Prop := fun l => ∀ n : Nat, (decodeAux n l).2.length ≤ l.length
  change P l
  refine WellFounded.induction (measure (fun l : List FormulaSym => l.length)).wf l ?_
  intro l ih
  dsimp [P] at ih ⊢
  intro n
  cases h : l with
  | nil => cases n <;> simp [decodeAux]
  | cons s l' =>
      cases n with
      | zero => simp [decodeAux]
      | succ n' =>
          cases s with
          | lit bl => rw [decodeAux_lit bl n' l']; change l'.length ≤ l'.length + 1; omega
          | varMark =>
              have h := decodeVar_suffix_le l'
              rw [decodeAux_varMark n' l']
              change (decodeVar l').2.length ≤ l'.length + 1
              omega
          | endMark => rw [decodeAux_endMark n' l']; change l'.length ≤ l'.length + 1; omega
          | notMark =>
              have h1 := ih l' (by rw [h]; change l'.length < l'.length + 1; omega) n'
              rw [decodeAux_notMark n' l']
              change (decodeAux n' l').2.length ≤ l'.length + 1
              omega
          | andMark =>
              have h1 := ih l' (by rw [h]; change l'.length < l'.length + 1; omega) n'
              let X : List FormulaSym := (decodeAux n' l').2
              have hXlen : X.length ≤ l'.length := by simpa [X] using h1
              have h2 := ih X (by rw [h]; change (decodeAux n' l').2.length < l'.length + 1; omega) n'
              rw [decodeAux_andMark n' l']
              change (decodeAux n' X).2.length ≤ l'.length + 1
              omega
          | orMark =>
              have h1 := ih l' (by rw [h]; change l'.length < l'.length + 1; omega) n'
              let X : List FormulaSym := (decodeAux n' l').2
              have hXlen : X.length ≤ l'.length := by simpa [X] using h1
              have h2 := ih X (by rw [h]; change (decodeAux n' l').2.length < l'.length + 1; omega) n'
              rw [decodeAux_orMark n' l']
              change (decodeAux n' X).2.length ≤ l'.length + 1
              omega
          | iffMark =>
              have h1 := ih l' (by rw [h]; change l'.length < l'.length + 1; omega) n'
              let X : List FormulaSym := (decodeAux n' l').2
              have hXlen : X.length ≤ l'.length := by simpa [X] using h1
              have h2 := ih X (by rw [h]; change (decodeAux n' l').2.length < l'.length + 1; omega) n'
              rw [decodeAux_iffMark n' l']
              change (decodeAux n' X).2.length ≤ l'.length + 1
              omega

end TM3CNF

end Turing

end Chapter34

end CLRS
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