Theorem 36, instance level — Definition 31 preserves validity and the number of solutions
ProvedNQueensComp.NPC.theorem_36_instancesLet be the construction of Definition 31, which sends an instance of Restricted 1-in-3-SAT (Problem 6) to an instance of Problem 5.
Claim (instance-level half of Theorem 36, p. 836). For every valid instance of Restricted 1-in-3-SAT (Problem 6), is a valid instance of Problem 5, and the two instances have the same number of solutions:
The paper proves this through Lemmas 33, 34 and 35, which give solution maps in both directions; the count equality needs in addition that these maps are mutually inverse on solutions. Cardinalities are Set.ncard (an infinite set would count as , but both sets here are finite).
This is one of the two halves of NQueensComp.NPC.theorem_36; the other, theorem_36_codes, is the statement about bit codes and polynomial-time computability.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from Claude (Anthropic).
import Mathlib import Definitions.Def_NQueensComp_NPC_Reductions
namespace NQueensComp.NPC
/-- Theorem 36, instance-level half. -/
theorem theorem_36_instances :
∀ cs : Inst6, Inst6Valid cs →
Inst5Valid (def31 cs) ∧
_root_.Set.ncard {Ss : List (Finset Queen) | Inst5IsSol (def31 cs) Ss} =
_root_.Set.ncard {T : Finset ℕ | Inst6IsSol cs T} := by sorry
end NQueensComp.NPC