Canonical counting tableau for the Cook–Levin verifier
DefinitionCountOrderings_NFree_CountingTableauExtend the Cook–Levin CNF with negative units for unreachable head positions at cell . A canonical CNF word counts assignments only to variables occurring in its formula. The normalized tableau is serialized with the existing Cook–Levin encoding.
Definition code
import Mathlib.Data.Set.Card
import Definitions.Def_CookLevin_Reduction
set_option autoImplicit false
open CookLevin
namespace CountOrderings.NFree
/-- Pin the extra right-move destination in the syntactic tableau. A run of length
`T` never has a head at cell `T+1`. -/
def boundaryUnits (sh : Shape) : Formula :=
(List.range (sh.T + 1)).flatMap fun t =>
(List.range sh.k).map fun j => [Literal.Neg (sh.headVar t j (sh.T + 1))]
/-- The Cook–Levin formula with the unreachable boundary variables fixed. -/
def parsimoniousTableau (sh : Shape) (M : Machine) (init : TapeIdx → ℕ → List Symbol) : Formula :=
tableauCNF sh M init ++ blankSuffixClauses sh 1 ++ boundaryUnits sh
/-- Count assignments on variables that occur in the CNF. -/
def formulaVars (φ : Formula) : Finset ℕ := (variablesList φ).toFinset
def liftAssignment {φ : Formula} (a : ↥(formulaVars φ) → Bool) : Assignment :=
fun n => if h : n ∈ formulaVars φ then a ⟨n, h⟩ else false
noncomputable def countCNFModel (φ : Formula) : ℕ :=
{ a : ↥(formulaVars φ) → Bool | Satisfies (liftAssignment a) φ }.ncard
/-- The number of satisfying assignments in a canonical CNF code, or zero on
malformed words. Only variables occurring in the formula are counted. -/
noncomputable def countEncodedCNF (x : List Bool) : ℕ :=
let φ := decodeFormula x
if encodeFormula φ = x then countCNFModel φ else 0
/-- The corrected counting tableau, serialized in the Cook–Levin formula encoding. -/
def countedCookLevinReduction (M : Machine) (k G cw dw ct dt : ℕ)
(x : List Bool) : List Bool :=
encodeFormula (parsimoniousTableau ⟨k, G, M.length, tabWidth cw dw ct dt x⟩ M
(reductionInit (boolsToSymbols x) (certLen cw dw x)))
end CountOrderings.NFree
Source
Cook–Levin tableau correspondence on the platform, https://prove2.me/theorems/b5d75d8e-6bbb-49a3-bd6d-e25ba880e328, counting refinement for the #X3C source of Theorem 6.3