Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The 3SAT verifier circuit accepts exactly the satisfiable instances

Proved
LatticePrepro.ThreeSAT.mem_language_iff

by WizardOfMenlo · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

For every number of variables vvv and every 3SAT instance xxx on vvv variables,

encode(x)∈L(circuitv)  ⟺  x is satisfiable.\mathrm{encode}(x) \in L(\mathrm{circuit}_v) \iff x \text{ is satisfiable}.encode(x)∈L(circuitv​)⟺x is satisfiable.

Here:

  • xxx is given by one bit for each of the (2v)3(2v)^3(2v)3 possible clauses (ordered triples of literals (i,s)(i, s)(i,s), with iii a variable and s∈{0,1}s \in \{0,1\}s∈{0,1} a sign), saying which clauses are present, and encode(x)∈{0,1}(2v)3\mathrm{encode}(x) \in \{0,1\}^{(2v)^3}encode(x)∈{0,1}(2v)3 lists these bits in a fixed enumeration of the clauses;
  • circuitv\mathrm{circuit}_vcircuitv​ is the 3SAT verifier circuit: (2v)3(2v)^3(2v)3 input wires, v+1v + 1v+1 witness wires (an assignment to the vvv variables and a dummy wire), and 7(2v)3+17(2v)^3 + 17(2v)3+1 gates evaluating "every present clause contains a literal satisfied by the assignment";
  • L(C)L(C)L(C) is the language of a circuit CCC: the inputs yyy for which some witness makes the output wire 111;
  • xxx is satisfiable if some assignment a∈{0,1}va \in \{0,1\}^va∈{0,1}v satisfies every clause present in xxx, i.e. each present clause has a literal (i,s)(i, s)(i,s) with ai=sa_i = sai​=s.

The proof of Theorem 5.1 takes "V=VnV = V_nV=Vn​, a verifier for 3SAT"; this theorem establishes that the concrete circuit used in the formalization is such a verifier. Combined with BoolCircuit.language_toGateVerifier and Claim 3.15, it yields a quadratic verifier whose language is the set of encodings of satisfiable instances, to which the general results apply (ThreeSAT.exists_code_gap, ThreeSAT.exists_lattice_gap).

Formalization Note: The statement holds for every vvv, with no lower bound. Polynomial-time constructibility of the circuit is not formalized; the size bound S≤9n+2S \le 9n + 2S≤9n+2 on its number of wires is a separate lemma. The encoding by one bit per possible clause follows the proof of Theorem 5.4 of the paper.

Preamble
import Mathlib
import Definitions.Def_LatticePrepro_Verifier_Quadratic
import Definitions.Def_LatticePrepro_Verifier_Gates
import Definitions.Def_LatticePrepro_Verifier_Circuit
import Definitions.Def_LatticePrepro_Verifier_Expr
import Definitions.Def_LatticePrepro_Verifier_ThreeSAT

open LatticePrepro
open LatticePrepro.ThreeSAT
variable {v : ℕ}
Formal statement
theorem LatticePrepro.ThreeSAT.mem_language_iff (x : Instance v) : encode x ∈ (circuit v).Language ↔ Satisfiable x := by sorry
Source
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), the verifier VnV_nVn​ for 3SAT in the proof of Theorem 5.1 (\label{thm:approximation-hardness}), with the instance encoding of the proof of Theorem 5.4 (\label{thm:explicit-endpoint}); Lean: LatticePrepro/Verifier/ThreeSAT.lean, LatticePrepro.ThreeSAT.mem_language_iff
Human review
  • Endorsed by Shuze Chen · Nov 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by WizardOfMenlo · Nov 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me