Theorem 4 (hardness half) — #Restricted 1-in-3-SAT is #P-hard
OpenNQueensComp.NPC.countRestricted1in3SAT_sharpPHardLet 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. is #P-hard under polynomial-time parsimonious reductions: for every there is a map , computable in polynomial time on the CookLevin machine model, with
This is the hardness half of Theorem 4 (p. 820). The paper cites Creignou and Hermann (1996) for #P-completeness of Monotone 1-in-3-SAT, and gives a parsimonious reduction from it that limits each variable to at most three occurrences. NP-hardness of the language follows from this statement, because a parsimonious reduction preserves whether the count is nonzero.
Formalization Note. Same encoding and readings as the parent NQueensComp.NPC.theorem_4. Hardness is SharpPHard: every InSharpP function reduces to the count through ParsimoniousReducible.
import Mathlib import Definitions.Def_NQueensComp_NPC_SharpP import Definitions.Def_NQueensComp_NPC_Codes
namespace NQueensComp.NPC /-- Theorem 4, p. 820, hardness half: counting the solutions of Restricted 1-in-3-SAT is #P-hard under polynomial-time parsimonious reductions. -/ theorem countRestricted1in3SAT_sharpPHard : SharpPHard countRestricted1in3SAT := by sorry end NQueensComp.NPC