Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: Scratch_PricingWithTips_FixedShapePaddingSelectorSemantics

Definition
PricingWithTips3DM_d15dc1bc5c68c26e893b7ba8

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

namespace PricingWithTips.FixedShapePaddingSelectorSemantics

open CLRS.Chapter34
open CLRS.Chapter34.Turing.VertexCover.ComplementMachine.NonedgeFilter
open PricingWithTips.FixedShape3DM
open PricingWithTips.FixedShapeClauseMembershipTM2
open PricingWithTips.FixedShapePaddingSelectorTM2
open PricingWithTips.FixedShapePaddingKeysTM2
open PricingWithTips.FixedShapeLiteralMembershipTM2

private theorem selectedEdges_append
    (left right : List (Nat × Nat)) (leftBits rightBits : List Bool)
    (h : left.length = leftBits.length) :
    Selector.selectedEdges (left ++ right) (leftBits ++ rightBits) =
      Selector.selectedEdges left leftBits ++
        Selector.selectedEdges right rightBits := by
  induction left generalizing leftBits with
  | nil =>
      have : leftBits = [] := List.eq_nil_of_length_eq_zero h.symm
      subst leftBits
      rfl
  | cons item left ih =>
      cases leftBits with
      | nil => simp at h
      | cons bit bits =>
          simp only [List.length_cons, Nat.succ.injEq] at h
          cases bit <;> simp [Selector.selectedEdges, ih bits h]

private theorem selectedEdges_map_not {α : Type}
    (items : List α) (value : α → Nat × Nat) (present : α → Bool) :
    Selector.selectedEdges (items.map value)
        ((items.map present).map Bool.not) =
      (items.filter fun item => present item).map value := by
  induction items with
  | nil => rfl
  | cons item items ih =>
      cases h : present item <;>
        simp [Selector.selectedEdges, h, List.map_map] at ih ⊢ <;>
        exact ih

theorem selectedPaddingEdges_eq (input : List CNFSym) :
    selectedPaddingEdges input =
      ((List.range input.length).filter fun q =>
          decide ((baseCNF input).length ≤ q)).map (fun q => (q, 0)) ++
      ((List.range input.length).filter fun q =>
          decide ((baseCNF input).length ≤ q)).map (fun q => (q, 1)) := by
  unfold selectedPaddingEdges Selector.alignedSelectedEdges
  simp only [PricingWithTips.FixedShapePaddingSelectorTM2.alignedInput,
    retainPaddingBits, duplicatedPaddingBits, allPaddingCandidates,
    paddingClauseMembershipBits_eq, List.map_append]
  rw [selectedEdges_append]
  · rw [selectedEdges_map_not, selectedEdges_map_not]
  · simp

theorem mem_selectedPaddingEdges_iff (input : List CNFSym)
    (edge : Nat × Nat) :
    edge ∈ selectedPaddingEdges input ↔
      ∃ q, q < input.length ∧ (baseCNF input).length ≤ q ∧
        (edge = (q, 0) ∨ edge = (q, 1)) := by
  rw [selectedPaddingEdges_eq]
  simp only [List.mem_append, List.mem_map, List.mem_filter,
    List.mem_range, decide_eq_true_eq]
  constructor
  · rintro (⟨q, ⟨hq, hbase⟩, rfl⟩ | ⟨q, ⟨hq, hbase⟩, rfl⟩)
    · exact ⟨q, hq, hbase, Or.inl rfl⟩
    · exact ⟨q, hq, hbase, Or.inr rfl⟩
  · rintro ⟨q, hq, hbase, rfl | rfl⟩
    · exact Or.inl ⟨q, ⟨hq, hbase⟩, rfl⟩
    · exact Or.inr ⟨q, ⟨hq, hbase⟩, rfl⟩

end PricingWithTips.FixedShapePaddingSelectorSemantics
Source
https://arxiv.org/abs/2507.10872

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