Logarithmic word width for sparse k-SAT computations
ProvedKSATSingleFlip.Connect.wordRAM_log_widthFor the candidate word-RAM model, if the sparse formula has clauses and the computation has at most steps, then each of the two declared word widths is at most
where the logarithms in this display are floor base-two logarithms. Thus for fixed the width is , ruling out unit-cost operations on superpolynomially large words in the intended linear and quadratic regimes. This statement concerns the model and does not prove an algorithm.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_WordRAM
Formal statement
namespace KSATSingleFlip.Connect
/-- Sparse linear input and quadratic budgets require logarithmic word width. -/
theorem wordRAM_log_width (n k m T c d : ℕ)
(hm : m ≤ c * n) (hT : T ≤ d * (n + 1)^2) :
wordRAMWidth n k m T ≤
Nat.log2 (k + c + 2*k*c + d + 13) + 2 * Nat.log2 (n + 1) + 5 ∧
wordRAMRouteWidth n k m T ≤
Nat.log2 (k + c + 2*k*c + d + 13) + 2 * Nat.log2 (n + 1) + 5 := by
sorry
end KSATSingleFlip.Connect
Source
Formalization choice for the runtime statements in Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, Theorem 1.3, printed p. 4 (PDF p. 6), STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf