Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_604e423cb2b06db74a24fbab

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_d4904298ab86e1b10dc4a2cf
import Definitions.Def_PricingWithTips3DM_b4f76447a6d2b46e80bcfdbb
import Definitions.Def_PricingWithTips3DM_dea1a793ff7c6a92846a13d9
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Indexed occurrence rows: semantics and core controller

Each literal occurrence becomes one marked unary row with fields for its
numeric vertex, clause, polarity, and positive variable-code length.  The
last field uses the literal encoding's existing `index + 1` convention.
-/

noncomputable section

namespace CLRS
namespace Chapter34
namespace Turing
namespace TMClique

open PolyBuilder

/-- Numeric polarity bit used by the row encoding. -/
def occurrencePolarityCode : Literal → Nat
  | .pos _ => 0
  | .neg _ => 1

/-- Positive unary variable code already present in the canonical CNF
encoding. -/
def occurrenceVariableCode : Literal → Nat
  | .pos index | .neg index => index + 1

/-- Four numeric fields of one indexed occurrence row. -/
def indexedOccurrenceRowValues (vertex : Nat)
    (occurrence : IndexedOccurrence) : List Nat :=
  [vertex, occurrence.clauseIndex, occurrencePolarityCode occurrence.literal,
    occurrenceVariableCode occurrence.literal]

/-- Marked rows for one clause, starting at the supplied global vertex. -/
def encodeIndexedClauseRowsFrom : Nat → Nat → Clause → List UnaryFrameSym
  | _, _, [] => []
  | vertex, clauseIndex, literal :: clause =>
      encodeUnaryFrame
          (indexedOccurrenceRowValues vertex
            { clauseIndex, positionIndex := 0, literal }) ++
        [.frameEnd] ++
        encodeIndexedClauseRowsFrom (vertex + 1) clauseIndex clause

/-- Marked rows for a formula suffix, starting at supplied vertex and clause
indices. -/
def encodeIndexedOccurrenceRowsFrom : Nat → Nat → CNF → List UnaryFrameSym
  | _, _, [] => []
  | vertex, clauseIndex, clause :: formula =>
      encodeIndexedClauseRowsFrom vertex clauseIndex clause ++
        encodeIndexedOccurrenceRowsFrom (vertex + clause.length)
          (clauseIndex + 1) formula

/-- Canonical marked rows for all literal positions of a formula. -/
def encodeIndexedOccurrenceRows (formula : CNF) : List UnaryFrameSym :=
  encodeIndexedOccurrenceRowsFrom 0 0 formula

/-- Indexed rows determined by an arbitrary raw CNF word. -/
def canonicalIndexedOccurrenceRows (input : List CNFSym) :
    List UnaryFrameSym :=
  encodeIndexedOccurrenceRows (decodeCNF input)

/-- Exact raw-input meaning of the indexed occurrence-row stream. -/
theorem canonicalIndexedOccurrenceRows_eq (input : List CNFSym) :
    canonicalIndexedOccurrenceRows input =
      encodeIndexedOccurrenceRows (decodeCNF input) := rfl

/-- Finite phases of the reverse-output occurrence-row controller. -/
inductive OccurrenceRowsLabel
  | scan (startedClause : Bool)
  | copyVertex | saveVertex | pushVertexTick | pushVertexSep
  | restoreVertex | restoreVertexInc
  | copyClause | saveClause | pushClauseTick | pushClauseSep
  | restoreClause | restoreClauseInc
  | readPolarity | pushNegativeTick | pushPolaritySep | readVariableMark
  | variableRun | pushVariableTick
  | saveBoundary (symbol : GraphSym) | restoreBoundary
  | pushVariableSep | pushRowEnd | advanceVertex
  | advanceClause
  | clearVertex | clearClause
  | halt | invalid
deriving DecidableEq, Fintype

/-- Reverse-output parser for canonical occurrence descriptors.  Counter one
stores the vertex ordinal, counter two the clause ordinal, and counter three
temporarily saves either ordinal while it is copied to the output. -/
def occurrenceRowsRevProgram : Program GraphSym UnaryFrameSym where
  Label := OccurrenceRowsLabel
  main := .scan false
  op
    | .scan started => .popInput .clearVertex fun
        | .clauseMark => if started then .advanceClause else .scan true
        | .vertexMark => .copyVertex
        | _ => .invalid
    | .copyVertex => .dec₁ .pushVertexSep .saveVertex
    | .saveVertex => .inc₃ .pushVertexTick
    | .pushVertexTick => .pushOutput .tick .copyVertex
    | .pushVertexSep => .pushOutput .separator .restoreVertex
    | .restoreVertex => .dec₃ .copyClause .restoreVertexInc
    | .restoreVertexInc => .inc₁ .restoreVertex
    | .copyClause => .dec₂ .pushClauseSep .saveClause
    | .saveClause => .inc₃ .pushClauseTick
    | .pushClauseTick => .pushOutput .tick .copyClause
    | .pushClauseSep => .pushOutput .separator .restoreClause
    | .restoreClause => .dec₃ .readPolarity .restoreClauseInc
    | .restoreClauseInc => .inc₂ .restoreClause
    | .readPolarity => .popInput .invalid fun
        | .posMark => .pushPolaritySep
        | .negMark => .pushNegativeTick
        | _ => .invalid
    | .pushNegativeTick => .pushOutput .tick .pushPolaritySep
    | .pushPolaritySep => .pushOutput .separator .readVariableMark
    | .readVariableMark => .popInput .invalid fun
        | .varMark => .variableRun
        | _ => .invalid
    | .variableRun => .popInput .pushVariableSep fun symbol =>
        if symbol = .endMark then .pushVariableTick else .saveBoundary symbol
    | .pushVariableTick => .pushOutput .tick .variableRun
    | .saveBoundary symbol => .pushWork₁ symbol .restoreBoundary
    | .restoreBoundary => .moveWork₁Input .pushVariableSep
        (fun _ => .pushVariableSep)
    | .pushVariableSep => .pushOutput .separator .pushRowEnd
    | .pushRowEnd => .pushOutput .frameEnd .advanceVertex
    | .advanceVertex => .inc₁ (.scan true)
    | .advanceClause => .inc₂ (.scan true)
    | .clearVertex => .dec₁ .clearClause .clearVertex
    | .clearClause => .dec₂ .halt .clearClause
    | .halt => .halt
    | .invalid => .halt

/-- Proof-facing occurrence-row configuration. -/
def occurrenceRowsCfg (label : OccurrenceRowsLabel)
    (buffer : Option GraphSym) (test : Bool)
    (input : List GraphSym) (output : List UnaryFrameSym)
    (work : List GraphSym) (vertex clause saved : Nat) :
    BuilderCfg occurrenceRowsRevProgram where
  label := some label
  buffer₁ := buffer
  buffer₂ := none
  test := test
  input := input
  output := output
  work₁ := work
  work₂ := []
  counter₁ := List.replicate vertex ()
  counter₂ := List.replicate clause ()
  counter₃ := List.replicate saved ()

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