3-SAT reductions and low-bit dissection complexity model
DefinitionAddXnor_Supplement_algorithmsThis module defines the exact algorithmic assertions used by Theorems 2 and 7. For Theorem 2 it records deterministic multitape-Turing computation, linear balanced output size, sparsified disjunction size, and running time. For Theorem 7 it defines the low-bit classes , their balance parameter
and a two-phase deterministic machine interface that computes before running the witness-producing solver with the claimed time and space bounds.
These definitions make the paper's asymptotic algorithmic clauses kernel-visible rather than treating “there is an algorithm” as an uninterpreted proposition.
Formalization Note is an explicit arbitrary polynomial factor in the encoded input length. Space bounds constrain every head and every nonblank cell throughout the multitape-machine trace.
import Mathlib
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_AddXnor_ADD_XNOR
import Definitions.Def_AddXnor_Supplement_core
set_option autoImplicit false
namespace AddXnor.Supplement
/-!
# Complexity objects for Theorems 2 and 7
Running time and space use the deterministic multitape Turing-machine semantics already used by
`CookLevin.IsPolyTimeComputable`. The exponential factors below are accompanied by an arbitrary
fixed polynomial in the binary input length, which is the paper's `O*` convention (p.6).
-/
/-- A CNF in which every clause has at most three literals. -/
def Is3CNF (φ : CookLevin.Formula) : Prop := ∀ C ∈ φ, C.length ≤ 3
/-- The number of distinct variables that actually occur in a formula. -/
def numVars (φ : CookLevin.Formula) : ℕ :=
(CookLevin.variablesList φ).eraseDups.length
/-- A bit string is the bare `n²`-bit encoding of `n` words of width `n`, whether or not the
resulting Add/XNOR instance is solvable. -/
def IsBalancedEncoding (w : List Bool) (n : ℕ) : Prop :=
∃ A : Fin n → BitVec n, 2 ≤ n ∧ w = (List.ofFn fun i => AddXnor.encWord (A i)).flatten
/-- The first, linear-parameter clause of Theorem 2. -/
def LinearThreeSATReduction (f : List Bool → List Bool) : Prop :=
CookLevin.IsPolyTimeComputable f ∧
∃ C : ℕ, 0 < C ∧ ∀ φ : CookLevin.Formula,
Is3CNF φ →
(CookLevin.Satisfiable φ ↔ AddXnor.ADD_XNOR (f (CookLevin.encodeFormula φ))) ∧
∃ n : ℕ, IsBalancedEncoding (f (CookLevin.encodeFormula φ)) n ∧
(0 < numVars φ + φ.length → n ≤ C * (numVars φ + φ.length))
/-- A self-delimiting encoding of a list of bit strings. -/
def encodeBatch (ws : List (List Bool)) : List Bool :=
CookLevin.encodeListNat (ws.map fun w =>
w.foldl (fun a b => 2 * a + if b then 1 else 0) 1)
/-- Integer time allowance for the factor `2^(ηv)`. -/
noncomputable def expBudget (η : ℝ) (v : ℕ) : ℕ :=
⌈Real.rpow 2 (η * v)⌉₊
/-- A batch constructor is computed by a deterministic multitape Turing machine in
`poly(input length) · 2^(ηv)` steps. The formula's exact number of occurring variables is `v`.
-/
def ComputableInSubexpTime (η : ℝ) (batch : CookLevin.Formula → List (List Bool)) : Prop :=
∃ (M : CookLevin.Machine) (tapes alphabet C d : ℕ),
CookLevin.TuringMachine tapes alphabet M ∧
∀ φ : CookLevin.Formula,
let input := CookLevin.encodeFormula φ
let B := C * (input.length + 1) ^ d * expBudget η (numVars φ)
(CookLevin.execute M
(CookLevin.startConfig2 tapes (CookLevin.boolsToSymbols input) []) B).1 = M.length ∧
CookLevin.outputOf tapes
(CookLevin.execute M
(CookLevin.startConfig2 tapes (CookLevin.boolsToSymbols input) []) B) (B + 2) =
encodeBatch (batch φ)
/-- The sparsification consequence in Theorem 2, including batch size, equivalence of the
disjunction, the linear balanced parameter of every output, and `O*(2^(ηv))` construction time. -/
def SparsifiedThreeSATReduction (η : ℝ) : Prop :=
∃ (batch : CookLevin.Formula → List (List Bool)) (Cη : ℕ),
0 < Cη ∧ ComputableInSubexpTime η batch ∧
∀ φ : CookLevin.Formula, Is3CNF φ →
((CookLevin.Satisfiable φ ↔ ∃ w ∈ batch φ, AddXnor.ADD_XNOR w) ∧
((batch φ).length : ℝ) ≤ Real.rpow 2 (η * numVars φ) ∧
∀ w ∈ batch φ, ∃ n : ℕ, IsBalancedEncoding w n ∧
(0 < numVars φ → n ≤ Cη * numVars φ))
/-! ## Low-bit dissection -/
/-- The inverse of one Add/XNOR step. Both branches are permutations of the word space. -/
def invStep {m : ℕ} (o : Bool) (s a : BitVec m) : BitVec m :=
if o then ~~~(s ^^^ a) else s - a
/-- The split point uses `k=floor(q/4)` and two blocks, hence `2k` prefix operators. -/
def quarter (q : ℕ) : ℕ := q / 4
/-- Forward middle state `S(u)` after the first `2k` operators. -/
def forwardMiddle {q m : ℕ} (A : Fin (q + 1) → BitVec m)
(u : Fin (2 * quarter q) → Bool) : BitVec m :=
AddXnor.chain (A 0)
(List.ofFn fun i : Fin (2 * quarter q) =>
(u i, A ⟨i + 1, by have := i.isLt; simp [quarter] at *; omega⟩))
/-- Backward middle state `R(v)`: the unique state from which the last `q-2k` operations reach
zero. The fold is right-to-left and uses the exact inverses of the published steps. -/
def backwardMiddle {q m : ℕ} (A : Fin (q + 1) → BitVec m)
(v : Fin (q - 2 * quarter q) → Bool) : BitVec m :=
(List.ofFn fun i : Fin (q - 2 * quarter q) =>
(v i, A ⟨2 * quarter q + i + 1, by have := i.isLt; omega⟩)).foldr
(fun oa s => invStep oa.1 s oa.2) 0
/-- Cardinality `|F_g|` of one low-bit prefix class. -/
def forwardClassCard {q m : ℕ} (A : Fin (q + 1) → BitVec m) (p : ℕ)
(g : Fin (2 ^ p)) : ℕ :=
((Finset.univ : Finset (Fin (2 * quarter q) → Bool)).filter fun u =>
(forwardMiddle A u).toNat % 2 ^ p = g).card
/-- Cardinality `|B_g|` of one low-bit suffix class. -/
def backwardClassCard {q m : ℕ} (A : Fin (q + 1) → BitVec m) (p : ℕ)
(g : Fin (2 ^ p)) : ℕ :=
((Finset.univ : Finset (Fin (q - 2 * quarter q) → Bool)).filter fun v =>
(backwardMiddle A v).toNat % 2 ^ p = g).card
/-- The balance parameter `μ_p = max_g min(|F_g|,|B_g|)`. -/
def balance {q m : ℕ} (A : Fin (q + 1) → BitVec m) (p : ℕ) : ℕ :=
(Finset.univ : Finset (Fin (2 ^ p))).sup fun g =>
min (forwardClassCard A p g) (backwardClassCard A p g)
/-- Encoding of a two-parameter Add/XNOR instance together with the dissection parameter `p`. -/
def encodeDissectionInput {q m : ℕ} (p : ℕ) (A : Fin (q + 1) → BitVec m) : List Bool :=
CookLevin.encodeNat q ++ CookLevin.encodeNat m ++ CookLevin.encodeNat p ++
(List.ofFn fun i => AddXnor.encWord (A i)).flatten
/-- Encoding of `none` (unsatisfiable) or of a witness operator string. -/
def encodeAnswer {q : ℕ} : Option (Fin q → Bool) → List Bool
| none => [false]
| some x => true :: List.ofFn x
/-- A returned answer is a correct decision together with a witness when one exists. -/
def CorrectAnswer {q m : ℕ} (A : Fin (q + 1) → BitVec m)
(ans : Option (Fin q → Bool)) : Prop :=
match ans with
| none => ¬ ∃ x : Fin q → Bool, eval A x = 0
| some x => eval A x = 0
/-- The number of states sufficient for the `2^(q/2)` and `2^(q/4)` factors. -/
def halfPow (q : ℕ) : ℕ := 2 ^ ((q + 1) / 2)
def quarterPow (q : ℕ) : ℕ := 2 ^ ((q + 3) / 4)
/-- A machine computes a requested bit-string output at the displayed exact time bound. -/
def MachineComputesAt (M : CookLevin.Machine) (tapes : ℕ) (input output : List Bool)
(time : ℕ) : Prop :=
(CookLevin.execute M
(CookLevin.startConfig2 tapes (CookLevin.boolsToSymbols input) []) time).1 = M.length ∧
CookLevin.outputOf tapes
(CookLevin.execute M
(CookLevin.startConfig2 tapes (CookLevin.boolsToSymbols input) []) time) (time + 2) = output
/-- The whole trace stays in the first `space+1` cells of every tape. -/
def MachineUsesSpaceAtMost (M : CookLevin.Machine) (tapes : ℕ) (input : List Bool)
(time space : ℕ) : Prop :=
∀ t ≤ time, ∀ tape < tapes,
CookLevin.headPos
(CookLevin.execute M
(CookLevin.startConfig2 tapes (CookLevin.boolsToSymbols input) []) t) tape ≤ space ∧
∀ cell, space < cell →
CookLevin.tapeFun
(CookLevin.execute M
(CookLevin.startConfig2 tapes (CookLevin.boolsToSymbols input) []) t) tape cell =
CookLevin.blankSymbol
/-- A uniform deterministic implementation of low-bit dissection. The preprocessing machine
first outputs the exact `μ_p` within `O*(2^(q/4))`; only then is that value supplied to the solver,
which decides and returns a witness within the theorem's total time and space bounds. -/
def IsLowBitDissectionAlgorithm : Prop :=
∃ (pre solve : CookLevin.Machine) (preTapes solveTapes alphabet C d : ℕ),
0 < C ∧ CookLevin.TuringMachine preTapes alphabet pre ∧
CookLevin.TuringMachine solveTapes alphabet solve ∧
∀ (q m p : ℕ) (A : Fin (q + 1) → BitVec m), 1 ≤ q → 1 ≤ m → p ≤ quarter q →
let input := encodeDissectionInput p A
let poly := C * (input.length + 1) ^ d
let preTime := poly * quarterPow q
let totalTime := poly * halfPow q
let totalSpace := poly * (quarterPow q + balance A p)
MachineComputesAt pre preTapes input (CookLevin.encodeNat (balance A p)) preTime ∧
MachineUsesSpaceAtMost pre preTapes input preTime (poly * quarterPow q) ∧
∃ ans : Option (Fin q → Bool), CorrectAnswer A ans ∧
MachineComputesAt solve solveTapes
(input ++ CookLevin.encodeNat (balance A p)) (encodeAnswer ans) totalTime ∧
MachineUsesSpaceAtMost solve solveTapes
(input ++ CookLevin.encodeNat (balance A p)) totalTime totalSpace
end AddXnor.Supplement