Parsimonious reduction from encoded #CNFSAT to indexed #X3C
ProvedCountOrderings.NFree.countEncodedCNF_parsimonious_to_x3cThere is a polynomial-time Cook–Levin transducer taking a canonical CNF word to an indexed exact-cover-by-triples word and preserving the number of solutions. Count satisfying assignments on the variables occurring in the formula. Both counting functions map malformed codes to zero.
Preamble
import Definitions.Def_CountOrderings_NFree_CountingTableau import Definitions.Def_CountOrderings_NFree_OracleReduction import Definitions.Def_NQueensComp_NPC_SharpP
Formal statement
namespace CountOrderings.NFree
theorem countEncodedCNF_parsimonious_to_x3c :
NQueensComp.NPC.ParsimoniousReducible countEncodedCNF x3cCount := by sorry
end CountOrderings.NFreeSource
Hunt, Marathe, Radhakrishnan and Stearns, The Complexity of Planar Counting Problems, https://doi.org/10.1137/S0097539793304601, Theorem 3.10 and Corollary 3.11