The 3SAT verifier circuit accepts exactly the satisfiable instances
ProvedLatticePrepro.ThreeSAT.mem_language_iffFor every number of variables and every 3SAT instance on variables,
Here:
- is given by one bit for each of the possible clauses (ordered triples of literals , with a variable and a sign), saying which clauses are present, and lists these bits in a fixed enumeration of the clauses;
- is the 3SAT verifier circuit: input wires, witness wires (an assignment to the variables and a dummy wire), and gates evaluating "every present clause contains a literal satisfied by the assignment";
- is the language of a circuit : the inputs for which some witness makes the output wire ;
- is satisfiable if some assignment satisfies every clause present in , i.e. each present clause has a literal with .
The proof of Theorem 5.1 takes ", 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 , with no lower bound. Polynomial-time constructibility of the circuit is not formalized; the size bound 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.
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 : ℕ}theorem LatticePrepro.ThreeSAT.mem_language_iff (x : Instance v) : encode x ∈ (circuit v).Language ↔ Satisfiable x := by sorry
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.