Theorem 4 (membership half) — #Restricted 1-in-3-SAT is in #P
OpenNQueensComp.NPC.countRestricted1in3SAT_inSharpPLet be the number of solutions of the instance of Restricted 1-in-3-SAT coded by the string (and if codes no valid instance). In Restricted 1-in-3-SAT every clause is a set of three distinct positive variables, every variable occurs in at most three clauses, and a solution is a truth assignment making exactly one variable of each clause true.
Claim. : there is a polynomial-time NP verifier on the CookLevin machine model such that for every string
This is the membership half of Theorem 4 (p. 820). Together with the hardness half (NQueensComp.NPC.countRestricted1in3SAT_sharpPHard) it gives the whole of Theorem 4, NP-completeness of the language included.
Formalization Note. Same encoding and readings as the parent NQueensComp.NPC.theorem_4: instances are ordered clause lists coded by CookLevin.encodeFormulaN (variables in unary), a solution is the set of true variables, and strings coding no valid instance have count . Membership is InSharpP.
import Mathlib import Definitions.Def_NQueensComp_NPC_SharpP import Definitions.Def_NQueensComp_NPC_Codes
namespace NQueensComp.NPC /-- Theorem 4, p. 820, membership half: counting the solutions of Restricted 1-in-3-SAT is in #P. -/ theorem countRestricted1in3SAT_inSharpP : InSharpP countRestricted1in3SAT := by sorry end NQueensComp.NPC