Theorem 2 — linear-parameter reduction from 3-SAT
OpenAddXnor.Supplement.theorem_2There is a deterministic polynomial-time reduction mapping every 3-CNF formula with occurring variables and clauses to an equivalent balanced Add/XNOR instance whose parameter satisfies .
Moreover, for every real , there is a constant and a deterministic procedure that, on a 3-CNF with variables, runs in time and outputs a disjunction of at most balanced Add/XNOR instances, each with in the positive-variable regime, whose disjunction is satisfiable exactly when the original formula is satisfiable.
This transfers fine-grained 3-SAT hardness to the balanced Add/XNOR parameter.
Formalization Note A clause has at most three literals, counts distinct variables that occur, and all time bounds use deterministic multitape Turing steps.
Differences from the source:
- encoding: asymptotic bounds and → correctness and well-formed output hold for every 3-CNF, while the pointwise size inequalities are guarded when their right-hand side is zero; reason: asymptotic notation imposes no pointwise zero-size target, whereas a balanced instance has
- encoding: deterministic time → an exact multitape-Turing bound equal to a fixed polynomial in the encoded input length times ; reason: this is the paper's stated bit-operation machine model and convention
import Mathlib import Definitions.Def_AddXnor_Supplement_algorithms set_option autoImplicit false
namespace AddXnor.Supplement
/-- **Theorem 2** (Wang, Lv, Shen, Zhang, *Add/XNOR Chains*, manuscript,
sha256 405d6dda..., Theorem 2, pp.12--13 (PDF pp.12--13)).
There is a deterministic polynomial-time reduction from 3-CNF to balanced Add/XNOR whose
balanced parameter is linear in the number of variables plus clauses. Moreover, at every
positive sparsification rate `η`, a deterministic `O*(2^(ηv))` procedure produces at most
`2^(ηv)` equivalent balanced instances, each of parameter at most `Cη v`.
**Formalization Note.** `v` is the number of variables that occur in the formula and `c` is its
number of clauses. Correctness and well-formed balanced output hold also at the empty boundary;
only the pointwise representatives of the asymptotic bounds `n ≤ C(v+c)` and `n ≤ Cηv` are
guarded when their right-hand side would be zero.
`ComputableInSubexpTime` uses deterministic multitape Turing steps and an arbitrary polynomial
factor in the input length, exactly the paper's `O*` convention. -/
theorem theorem_2 :
(∃ f : List Bool → List Bool, LinearThreeSATReduction f) ∧
∀ η : ℝ, 0 < η → SparsifiedThreeSATReduction η := by sorry
end AddXnor.Supplement