NAEtoColor.NAEtoColorCompleteness
theoremverifiedimported Lean
Completeness of the NAE-SAT to 3-coloring reduction. Let $f$ be a NAE-SAT instance over a variable type $V$, that is, a list of not-all-equal clauses each naming three variables. If $f$ is satisfiable — some Boolean assignment $V \to \{\mathrm{true}, \mathrm{false}\}$ makes the three variables of every clause not all receive the same value — then the reduction graph of $f$ is 3-colorable, meaning it admits a proper coloring with the three colors $\{0, 1, 2\}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma NAEtoColor.NAEtoColorCompleteness {V : Type} (f : NAESat3 V) : IsSatisfiable f → Is3Colorable (ReductionGraph f)
- Source
- TCSlib, `NAEtoColor.NAEtoColorCompleteness`
- Lean proof
- By CS 294-268 course staff (UC Berkeley, Spring 2026), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 UC Berkeley CS 294. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.NAEtoColor.NAEtoColorCompleteness← NAEtoColor.NAEtoColorCompleteness (TCSlib/Complexity/NPReductions/NAESATToColoring.lean:230): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- NAEtoColor.NAEclauseA Not-All-Equal Clause
- NAEtoColor.clauseNodeColorGiven three Boolean values $a, b, c$ (the truth values of a clause's three literals) and an index $k \in \mathrm{Fin}\,3$, returns the…
- NAEtoColor.OutputVertexThe vertex set of the reduction graph is an inductive type with three constructors:
• $\mathtt{groundNode}$ --- a… - NAEtoColor.SatisfiesClauseGiven a Boolean assignment $\mathit{assign} : V \to \mathtt{Bool}$ and a Not-All-Equal clause $c$ with three variables…
- NAEtoColor.naeColoringGiven a Boolean assignment $\mathit{assign} : V \to \mathtt{Bool}$, defines a coloring of all vertices of the reduction graph by:…
- NAEtoColor.NAESat3A NAE-SAT instance over variable type $V$ is defined as a list of NAE clauses, i.e.\…
- NAEtoColor.ReductionGraphGiven a NAE-SAT instance $f$, $\texttt{NAEtoColor.ReductionGraph}\;f$ is the simple graph on $\texttt{NAEtoColor.OutputVertex}\;V$ whose…
- NAEtoColor.IsSatisfiableA NAE-SAT instance $f$ over variable type $V$ is satisfiable if there exists a Boolean assignment…
- NAEtoColor.EdgeRelationGiven a NAE-SAT instance $\mathit{clauses}$, the directed edge relation on $\texttt{NAEtoColor.OutputVertex}\;V$ is defined by: (1)…
- NAEtoColor.Is3ColorableA simple graph $G$ on vertex type $V'$ is 3-colorable if there exists a proper coloring $G.\mathtt{Coloring}\;(\mathrm{Fin}\,3)$,…
- NAEtoColor.SatisfiesNAE3Given an assignment $\mathit{assign} : V \to \mathtt{Bool}$ and a NAE-SAT instance $f$, $\texttt{NAEtoColor.SatisfiesNAE3}$ returns…
- Used by 1
- NAEtoColor.NAEtoColorReductionCorrectness of the NAE-SAT to 3-coloring reduction. Let $f$ be a NAE-SAT instance over a variable type $V$, and let $\Gamma(f)$ denote its…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- Completeness of reduction from NAE-SAT to 3-Coloring. -/lemma NAEtoColor.NAEtoColorCompleteness {V : Type} (f : NAESat3 V) : IsSatisfiable f → Is3Colorable (ReductionGraph f) := by intro ⟨assign, hsat⟩ refine ⟨⟨naeColoring assign, ?_⟩⟩ intro u v hadj simp only [SimpleGraph.top_adj] obtain ⟨hne, hedge⟩ := hadj -- Prove for any directed edge; then handle both directions suffices ∀ {a b : OutputVertex V}, EdgeRelation f a b → naeColoring assign a ≠ naeColoring assign b by rcases hedge with h | h' · exact this h · exact fun heq => this h' heq.symm intro a b h match a, b with -- There are 6 cases to match: -- 1. Ground node : Ground node (no edge) | .groundNode, .groundNode => exact False.elim h -- 2. Ground node : Var node | .groundNode, .varNode v | .varNode v, .groundNode => simp only [naeColoring] cases assign v <;> simp -- 3. Ground node : Clause node (no edge) | .groundNode, .clauseNode _ _ | .clauseNode _ _, .groundNode => exact False.elim h -- 4. Var node : Var node (no edge) | .varNode v, .varNode w => exact False.elim h -- 5. Var node : Clause node | .varNode v, .clauseNode c k | .clauseNode c k, .varNode v => simp only [EdgeRelation] at h simp only [naeColoring] -- After rcases, k is substituted to 0, 1, or 2 by the rfl rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ <;> (cases assign c.v0 <;> cases assign c.v1 <;> cases assign c.v2 <;> simp [clauseNodeColor]) -- 6. Clause node : Clause node | .clauseNode c1 i, .clauseNode c2 j => obtain ⟨rfl, hcIn, hij⟩ := h simp only [naeColoring] have hNAE : SatisfiesClause assign c1 = true := List.all_eq_true.mp hsat c1 hcIn -- Case-split on both indices and all boolean assignments. -- Diagonal (i=j): hij gives contradiction. Non-diagonal non-NAE: hNAE gives contradiction. fin_cases i <;> fin_cases j <;> cases h0 : assign c1.v0 <;> cases h1 : assign c1.v1 <;> cases h2 : assign c1.v2 <;> simp_all [clauseNodeColor, SatisfiesClause]