Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralClique.OccurrenceReduction.Machine.Normalize

Definition
PricingWithTips3DM_a0617eb55b13f160277f4218

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_b96f43df0f03fac823d4c3fd
import Definitions.Def_PricingWithTips3DM_d8886977e67d59ff4f35de9d
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# A concrete CNF normalization pass for the general-CLIQUE reduction

The project source language deliberately gives malformed `CNFSym` strings a
total junk-decoding semantics.  Before occurrence enumeration, one fixed
finite-state transducer turns that raw input into the canonical serialization
of its decoded CNF.  At most two symbols of look-ahead are delayed; the final
action flushes such pending malformed prefixes.
-/

noncomputable section

namespace CLRS
namespace Chapter34
namespace Turing
namespace TMClique

open PolyBuilder

/-- Finite parser modes.  The Boolean records negative polarity. -/
inductive CNFNormalizeMode
  | outside
  | clause
  | pendingPolarity (negative : Bool)
  | pendingVariable (negative : Bool)
  | variableIndex
deriving DecidableEq, Fintype, Repr

/-- Canonical encoding of the junk literal used by `decodeLit`. -/
def junkLiteralEncoding : List CNFSym :=
  [.posMark, .varMark, .endMark]

private def normalizedPolarity (negative : Bool) : CNFSym :=
  if negative then .negMark else .posMark

/-- Process one symbol known to occur at a clause-literal boundary. -/
def normalizeClauseAction (symbol : CNFSym) :
    List CNFSym × CNFNormalizeMode :=
  match symbol with
  | .clauseMark => ([.clauseMark], .clause)
  | .posMark => ([], .pendingPolarity false)
  | .negMark => ([], .pendingPolarity true)
  | .varMark | .endMark => (junkLiteralEncoding, .clause)

/-- Fixed finite-state action implementing the permissive decoder exactly. -/
def cnfNormalizeAction : CNFNormalizeMode → CNFSym →
    List CNFSym × CNFNormalizeMode
  | .outside, .clauseMark => ([.clauseMark], .clause)
  | .outside, _ => ([], .outside)
  | .clause, symbol => normalizeClauseAction symbol
  | .pendingPolarity negative, .varMark =>
      ([], .pendingVariable negative)
  | .pendingPolarity _, symbol =>
      let next := normalizeClauseAction symbol
      (junkLiteralEncoding ++ next.1, next.2)
  | .pendingVariable negative, .endMark =>
      ([normalizedPolarity negative, .varMark, .endMark], .variableIndex)
  | .pendingVariable _, symbol =>
      let next := normalizeClauseAction symbol
      (junkLiteralEncoding ++ junkLiteralEncoding ++ next.1, next.2)
  | .variableIndex, .endMark => ([.endMark], .variableIndex)
  | .variableIndex, symbol => normalizeClauseAction symbol

/-- Flush delayed malformed prefixes at end of input. -/
def cnfNormalizeFinish : CNFNormalizeMode → List CNFSym
  | .pendingPolarity _ => junkLiteralEncoding
  | .pendingVariable _ => junkLiteralEncoding ++ junkLiteralEncoding
  | _ => []

/-- Finite-state normalization specification. -/
def cnfNormalizeSpec :
    StatefulFlatMapSpec CNFNormalizeMode CNFSym CNFSym where
  initial := .outside
  action := cnfNormalizeAction
  finish := cnfNormalizeFinish

@[simp] theorem cnfNormalizeSpec_action (mode : CNFNormalizeMode)
    (symbol : CNFSym) :
    cnfNormalizeSpec.action mode symbol = cnfNormalizeAction mode symbol := rfl

@[simp] theorem cnfNormalizeSpec_finish (mode : CNFNormalizeMode) :
    cnfNormalizeSpec.finish mode = cnfNormalizeFinish mode := rfl

/-- Observable output of the normalization controller. -/
def normalizeCNFInput (input : List CNFSym) : List CNFSym :=
  rewriteStatefulFlatMap cnfNormalizeSpec input

/-! ## A structural specification for the five parser modes -/

mutual
  /-- Canonical continuation while positioned at a literal boundary. -/
  def normalizeClauseStream : List CNFSym → List CNFSym
    | [] => []
    | .clauseMark :: rest => .clauseMark :: normalizeClauseStream rest
    | .posMark :: .varMark :: .endMark :: rest =>
        .posMark :: .varMark :: .endMark :: normalizeVariableIndexStream rest
    | .negMark :: .varMark :: .endMark :: rest =>
        .negMark :: .varMark :: .endMark :: normalizeVariableIndexStream rest
    | _ :: rest => junkLiteralEncoding ++ normalizeClauseStream rest
  termination_by input => (input.length, 0)
  decreasing_by all_goals simp_wf; omega

  /-- Copy the remaining unary index and resume at a literal boundary. -/
  def normalizeVariableIndexStream : List CNFSym → List CNFSym
    | .endMark :: rest => .endMark :: normalizeVariableIndexStream rest
    | input => normalizeClauseStream input
  termination_by input => (input.length, 1)
  decreasing_by all_goals simp_wf; omega
end

/-- Structural normalization before the first clause marker. -/
def normalizeTopStream : List CNFSym → List CNFSym
  | [] => []
  | .clauseMark :: rest => .clauseMark :: normalizeClauseStream rest
  | _ :: rest => normalizeTopStream rest

/-- Structural target denoted by each finite parser mode. -/
def normalizeModeStream : CNFNormalizeMode → List CNFSym → List CNFSym
  | .outside, input => normalizeTopStream input
  | .clause, input => normalizeClauseStream input
  | .pendingPolarity negative, input =>
      normalizeClauseStream (normalizedPolarity negative :: input)
  | .pendingVariable negative, input =>
      normalizeClauseStream
        (normalizedPolarity negative :: .varMark :: input)
  | .variableIndex, input => normalizeVariableIndexStream input

private theorem rewriteCNFNormalizeFrom_eq_modeStream
    (mode : CNFNormalizeMode) (input : List CNFSym) :
    rewriteStatefulFlatMapFrom cnfNormalizeSpec mode input =
      normalizeModeStream mode input := by
  induction input generalizing mode with
  | nil =>
      cases mode with
      | outside | clause | variableIndex =>
          simp [rewriteStatefulFlatMapFrom, cnfNormalizeFinish,
            normalizeModeStream, normalizeTopStream, normalizeClauseStream,
            normalizeVariableIndexStream]
      | pendingPolarity negative | pendingVariable negative =>
          cases negative <;>
            simp [rewriteStatefulFlatMapFrom, cnfNormalizeFinish,
              normalizeModeStream, normalizeClauseStream,
              junkLiteralEncoding, normalizedPolarity]
  | cons symbol rest ih =>
      cases mode with
      | outside | clause | variableIndex =>
          cases symbol <;>
            simp [rewriteStatefulFlatMapFrom, cnfNormalizeAction,
              normalizeClauseAction, normalizeModeStream,
              normalizeTopStream, normalizeClauseStream,
              normalizeVariableIndexStream, junkLiteralEncoding,
              normalizedPolarity, ih]
      | pendingPolarity negative | pendingVariable negative =>
          cases negative <;> cases symbol <;>
            simp [rewriteStatefulFlatMapFrom, cnfNormalizeAction,
              normalizeClauseAction, normalizeModeStream,
              normalizeClauseStream,
              junkLiteralEncoding, normalizedPolarity, ih]

theorem normalizeCNFInput_eq_normalizeTopStream (input : List CNFSym) :
    normalizeCNFInput input = normalizeTopStream input := by
  exact rewriteCNFNormalizeFrom_eq_modeStream .outside input

/-! ## Connection to the project's total CNF decoder -/

private theorem decodeCNFVarIdx_add (start : Nat) (input : List CNFSym) :
    decodeCNFVarIdx start input =
      let decoded := decodeCNFVarIdx 0 input
      (start + decoded.1, decoded.2) := by
  induction input generalizing start with
  | nil => simp [decodeCNFVarIdx]
  | cons symbol rest ih =>
      cases symbol with
      | endMark =>
          simp only [decodeCNFVarIdx]
          rw [ih (start + 1), ih 1]
          rcases hdecoded : decodeCNFVarIdx 0 rest with ⟨count, suffix⟩
          simp [Nat.add_assoc]
      | clauseMark | posMark | negMark | varMark =>
          simp [decodeCNFVarIdx]

private theorem normalizeVariableIndexStream_eq (input : List CNFSym) :
    normalizeVariableIndexStream input =
      let decoded := decodeCNFVarIdx 0 input
      List.replicate decoded.1 CNFSym.endMark ++
        normalizeClauseStream decoded.2 := by
  induction input with
  | nil => simp [normalizeVariableIndexStream, decodeCNFVarIdx]
  | cons symbol rest ih =>
      cases symbol with
      | endMark =>
          simp only [normalizeVariableIndexStream, decodeCNFVarIdx]
          rw [decodeCNFVarIdx_add 1 rest, ih]
          rcases hdecoded : decodeCNFVarIdx 0 rest with ⟨count, suffix⟩
          simp [List.replicate_succ, Nat.add_comm]
      | clauseMark | posMark | negMark | varMark =>
          simp [normalizeVariableIndexStream, decodeCNFVarIdx]

/-- Canonical encoding of the decoded current clause followed by all later
decoded clauses. -/
def encodeDecodedClauseStream (input : List CNFSym) : List CNFSym :=
  (decodeLits input).1.flatMap encLit ++
    encCNF (decodeCNF (decodeLits input).2)

private theorem normalizeClauseStream_eq_encodeDecodedClauseStream
    (input : List CNFSym) :
    normalizeClauseStream input = encodeDecodedClauseStream input := by
  let P : List CNFSym → Prop := fun symbols =>
    normalizeClauseStream symbols = encodeDecodedClauseStream symbols
  have hwf : ∀ n : Nat, ∀ symbols : List CNFSym,
      symbols.length = n → P symbols := by
    intro n
    induction n using Nat.strong_induction_on with
    | h n ih =>
        intro symbols hlength
        cases symbols with
        | nil =>
            simp [P, normalizeClauseStream, encodeDecodedClauseStream,
              decodeLits, decodeCNF, encCNF]
        | cons symbol rest =>
            have hrest : P rest :=
              ih rest.length (by simp at hlength; omega) rest rfl
            cases symbol with
            | clauseMark =>
                simp [P, normalizeClauseStream, encodeDecodedClauseStream,
                  decodeLits, decodeCNF, encCNF, encClause, hrest]
            | varMark | endMark =>
                simp [P, normalizeClauseStream, encodeDecodedClauseStream,
                  decodeLits, decodeLit, junkLiteralEncoding, encLit,
                  litSym, litIndex, hrest]
            | posMark =>
                cases rest with
                | nil =>
                    simp [P, normalizeClauseStream, encodeDecodedClauseStream,
                      decodeLits, decodeLit, junkLiteralEncoding, encLit,
                      litSym, litIndex, decodeCNF, encCNF]
                | cons second tail =>
                    cases second with
                    | clauseMark | posMark | negMark | endMark =>
                        simpa [P, normalizeClauseStream,
                          encodeDecodedClauseStream, decodeLits, decodeLit,
                          junkLiteralEncoding, encLit, litSym, litIndex] using
                          hrest
                    | varMark =>
                        cases tail with
                        | nil =>
                            simpa [P, normalizeClauseStream,
                              encodeDecodedClauseStream, decodeLits,
                              decodeLit, junkLiteralEncoding, encLit,
                              litSym, litIndex] using hrest
                        | cons third more =>
                            cases third with
                            | clauseMark | posMark | negMark | varMark =>
                                simpa [P, normalizeClauseStream,
                                  encodeDecodedClauseStream, decodeLits,
                                  decodeLit, junkLiteralEncoding, encLit,
                                  litSym, litIndex] using hrest
                            | endMark =>
                                rcases hdecoded : decodeCNFVarIdx 0 more with
                                  ⟨index, suffix⟩
                                have hsuffixLength : suffix.length ≤ more.length := by
                                  have hle := decodeCNFVarIdx_suffix_le 0 more
                                  simpa [hdecoded] using hle
                                have hsuffix : P suffix :=
                                  ih suffix.length (by
                                    simp at hlength
                                    omega) suffix rfl
                                have hindex :=
                                  normalizeVariableIndexStream_eq more
                                rw [hdecoded] at hindex
                                simp [P, normalizeClauseStream,
                                  encodeDecodedClauseStream, decodeLits,
                                  decodeLit, hdecoded, hindex, hsuffix,
                                  encLit, litSym, litIndex,
                                  List.replicate_succ]
            | negMark =>
                cases rest with
                | nil =>
                    simp [P, normalizeClauseStream, encodeDecodedClauseStream,
                      decodeLits, decodeLit, junkLiteralEncoding, encLit,
                      litSym, litIndex, decodeCNF, encCNF]
                | cons second tail =>
                    cases second with
                    | clauseMark | posMark | negMark | endMark =>
                        simpa [P, normalizeClauseStream,
                          encodeDecodedClauseStream, decodeLits, decodeLit,
                          junkLiteralEncoding, encLit, litSym, litIndex] using
                          hrest
                    | varMark =>
                        cases tail with
                        | nil =>
                            simpa [P, normalizeClauseStream,
                              encodeDecodedClauseStream, decodeLits,
                              decodeLit, junkLiteralEncoding, encLit,
                              litSym, litIndex] using hrest
                        | cons third more =>
                            cases third with
                            | clauseMark | posMark | negMark | varMark =>
                                simpa [P, normalizeClauseStream,
                                  encodeDecodedClauseStream, decodeLits,
                                  decodeLit, junkLiteralEncoding, encLit,
                                  litSym, litIndex] using hrest
                            | endMark =>
                                rcases hdecoded : decodeCNFVarIdx 0 more with
                                  ⟨index, suffix⟩
                                have hsuffixLength : suffix.length ≤ more.length := by
                                  have hle := decodeCNFVarIdx_suffix_le 0 more
                                  simpa [hdecoded] using hle
                                have hsuffix : P suffix :=
                                  ih suffix.length (by
                                    simp at hlength
                                    omega) suffix rfl
                                have hindex :=
                                  normalizeVariableIndexStream_eq more
                                rw [hdecoded] at hindex
                                simp [P, normalizeClauseStream,
                                  encodeDecodedClauseStream, decodeLits,
                                  decodeLit, hdecoded, hindex, hsuffix,
                                  encLit, litSym, litIndex,
                                  List.replicate_succ]
  exact hwf input.length input rfl

private theorem normalizeTopStream_eq_encCNF_decodeCNF
    (input : List CNFSym) :
    normalizeTopStream input = encCNF (decodeCNF input) := by
  induction input with
  | nil => simp [normalizeTopStream, decodeCNF, encCNF]
  | cons symbol rest ih =>
      cases symbol with
      | clauseMark =>
          simp [normalizeTopStream, decodeCNF, encCNF, encClause,
            normalizeClauseStream_eq_encodeDecodedClauseStream,
            encodeDecodedClauseStream]
      | posMark | negMark | varMark | endMark =>
          simpa [normalizeTopStream, decodeCNF] using ih

/-- Exact all-input semantics of the concrete normalization TM2. -/
theorem normalizeCNFInput_eq_encCNF_decodeCNF (input : List CNFSym) :
    normalizeCNFInput input = encCNF (decodeCNF input) := by
  rw [normalizeCNFInput_eq_normalizeTopStream,
    normalizeTopStream_eq_encCNF_decodeCNF]

/-- The normalization stream is computed by one fixed polynomial-time TM2. -/
noncomputable def normalizeCNFInput_computableInPolyTime :
    _root_.Turing.TM2ComputableInPolyTime id id normalizeCNFInput :=
  statefulFlatMap_computableInPolyTime cnfNormalizeSpec

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