Sparse k-SAT clauses preserve the formula semantics
ProvedKSATSingleFlip.Connect.sparse_clause_semanticsA sparse width- clause has exactly variables and is satisfied exactly when one of its stored literals is true. Every proper -clause has a sparse encoding, and every indexed formula has an encoding preserving clause order and multiplicity. This statement concerns semantic equivalence, not uniform sampling or runtime.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_SparseFlip open scoped Classical BigOperators open OAI.FixedClauseThreshold
Formal statement
namespace KSATSingleFlip.Connect
/-- Sparse k-clauses have exactly the original proper-clause semantics. -/
theorem sparse_clause_semantics (n k m : ℕ) :
(∀ C : SparseClause n k, (vbl C.toClause).card = k) ∧
(∀ (C : SparseClause n k) (x : Fin n → Bool), ClauseSat x C.toClause ↔ C.Sat x) ∧
(∀ D : ProperClause n k, ∃ C : SparseClause n k, C.toClause = D.val) ∧
(∀ F : Formula n k m, ∃ G : SparseFormula n k m, sparseFormulaSemantics G = ofFormula F) := by
sorry
end KSATSingleFlip.Connect
Source
Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, model printed p. 2 and compact path representation printed p. 32 (PDF p. 34), STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf