Binary-constraint tables over fixed finite alphabets reduce to ordinary CNF
ProvedPvsNP.finite_csp_to_cnfalgorithmsclusteringcomputational-complexity
A labels-at-each-vertex formula and the clauses forbidding incompatible label pairs encode satisfiability of an explicitly represented binary CSP. The translation is a time-bounded multistack program in the OAI binary coding. The alphabet is fixed independently of table size.
Preamble
import Definitions.Def_PvsNP import Definitions.Def_OAIQ053K052 open OAI.MetricKMedian.Binary.Automatic OAI.MetricKMedian.PCP.Compiler
Formal statement
theorem PvsNP.finite_csp_to_cnf {A : Type} [Fintype A] [DecidableEq A] [Inhabited A] :
∃ f : CSPTable A → PvsNP.CNF, Poly f ∧
∀ (t : CSPTable A) (h : t.WellFormed), PvsNP.Satisfiable (f t) ↔ ∃ a, (t.csp h).Satisfies a := by
sorry
Source
The finite binary constraint formalization of the openai/math metric k-median project (PCP.Compiler.CSPTable). The direct one-hot CNF encoding of a finite constraint problem.