NAEtoColor.clauseNodeColor
defimported Lean
Given 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 color in $\mathrm{Fin}\,3$ assigned to the $k$-th internal clause-gadget node. The coloring is chosen so that all three gadget nodes receive distinct colors whenever $(a, b, c)$ is a NAE-satisfying assignment; if the assignment is not NAE-satisfying, all gadget nodes are colored $0$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in def NAEtoColor.clauseNodeColor (a b c : Bool) (k : Fin 3) : Fin 3
- Defined in
- TCSlib, `NAEtoColor.clauseNodeColor`
- 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.clauseNodeColor← NAEtoColor.clauseNodeColor (TCSlib/Complexity/NPReductions/NAESATToColoring.lean:208): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 6
- Lorentz.SL2C.rotationZToAxisThe
SL(2,ℂ)rotation carrying thez-axis to axisi. - 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…
- NAEtoColor.naeColoringGiven a Boolean assignment $\mathit{assign} : V \to \mathtt{Bool}$, defines a coloring of all vertices of the reduction graph by:…
- SMRHN.SMThe ACC system for the SM plus RHN.
- PureU1.permThreeInjGiven three distinct elements an embedding of
Fin 3intoFin n. - lorentzAlgebra.rotationGeneratorThe rotation generator J_i in the Lorentz algebra so(1,3). This matrix generates infinitesimal rotations about the i-th axis following the…
- Lorentz.SL2C.rotationZToAxisThe
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in /-- Coloring of clause nodes obtained via reduction from NAE-SAT. Given the boolean values of the three literals in a clause, assigns colors to the three internal clause-gadget nodes. We do not assume that the clause is in the NAE-SAT instance. If the variables do not satisfy the Not-All-Equal clause, we color everything 0. This is a valid coloring since there are no edges between clause nodes in that case, and all variable nodes are colored either 1 or 2. -/ def NAEtoColor.clauseNodeColor (a b c : Bool) (k : Fin 3) : Fin 3 := match a, b, c with | true, true, false => match k with | 0 => 0 | 1 => 2 | 2 => 1 | true, false, true => match k with | 0 => 0 | 1 => 1 | 2 => 2 | false, true, true => match k with | 0 => 1 | 1 => 0 | 2 => 2 | true, false, false => match k with | 0 => 2 | 1 => 0 | 2 => 1 | false, true, false => match k with | 0 => 0 | 1 => 2 | 2 => 1 | false, false, true => match k with | 0 => 0 | 1 => 1 | 2 => 2 | _, _, _ => 0 -- (non-NAE cases have no clause-clause edges)