NAEtoColor.naeColoring
defimported Lean
Given a Boolean assignment $\mathit{assign} : V \to \mathtt{Bool}$, defines a coloring of all vertices of the reduction graph by: $\mathtt{groundNode} \mapsto 0$; $\mathtt{varNode}\;v \mapsto 1$ if $\mathit{assign}(v) = \mathtt{true}$, else $2$; $\mathtt{clauseNode}\;c\;k \mapsto \texttt{NAEtoColor.clauseNodeColor}\;(\mathit{assign}(c.v_0))\;(\mathit{assign}(c.v_1))\;(\mathit{assign}(c.v_2))\;k$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in def NAEtoColor.naeColoring {V : Type} (assign : V → Bool) : OutputVertex V → Fin 3
- Defined in
- TCSlib, `NAEtoColor.naeColoring`
- 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.naeColoring← NAEtoColor.naeColoring (TCSlib/Complexity/NPReductions/NAESATToColoring.lean:224): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 3
- 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…
- Used by 1
- NAEtoColor.NAEtoColorCompletenessCompleteness 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…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in /-- Coloring of entire simple graph obtained via reduction from NAE-SAT. Coloring constructed from NAE-SAT assignment. • groundNode ↦ 0 • varNode v ↦ 1 if assign v = true, else 2 • clauseNode c k ↦ clauseNodeColor (assign values of the 3 variables) -/ def NAEtoColor.naeColoring {V : Type} (assign : V → Bool) : OutputVertex V → Fin 3 | .groundNode => 0 | .varNode v => if assign v then 1 else 2 | .clauseNode c k => clauseNodeColor (assign c.v0) (assign c.v1) (assign c.v2) k