A constant-step sparse RAM program for the empty formula
ProvedKSATSingleFlip.Connect.wordRAM_empty_formula_flipIn the candidate fixed-width word-RAM model, a single deterministic program works for every zero-clause formula, initial assignment, and requested variable. It halts within twelve steps and returns the compact path consisting of that one flip. The path satisfies the empty formula and reverses the requested variable. This verifies a concrete base case of the computational model; it does not solve the general Theorem 1.3 algorithm.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_WordRAM
Formal statement
namespace KSATSingleFlip.Connect
/-- A concrete constant-step program solves all zero-clause flip requests. -/
theorem wordRAM_empty_formula_flip :
∃ program : WordRAMProgram, ∀ (n k : ℕ) (F : SparseFormula n k 0)
(x : Fin n → Bool) (v : Fin n),
wordRAMFlipResult program 12 F x v = some ⟨x, [v]⟩ ∧
(FlipListPath.mk x [v]).Satisfies (sparseFormulaSemantics F) ∧
(FlipListPath.mk x [v]).terminal v ≠ x v := by
sorry
end KSATSingleFlip.Connect
Source
Base case motivated by Theorem 1.3(a), Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, printed p. 4 (PDF p. 6), STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf. The paper does not prescribe this instruction set.