Theorem 19, instance level — Definition 16 preserves validity and the number of solutions
ProvedNQueensComp.NPC.theorem_19_instancesLet be the construction of Definition 16, which sends an instance of Problem 4 (Excluded Diagonals) to an instance of Problem 3.
Claim (instance-level half of Theorem 19, p. 827). For every valid instance of Problem 4 (Excluded Diagonals), is a valid instance of Problem 3, and the two instances have the same number of solutions:
The paper proves this through Lemmas 17 and 18, 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_19; the other, theorem_19_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 19, instance-level half. -/
theorem theorem_19_instances :
∀ M : Inst4, M.Valid →
(def16 M).Valid ∧
_root_.Set.ncard {S : Finset Queen | (def16 M).IsSol S} =
_root_.Set.ncard {S : Finset Queen | M.IsSol S} := by sorry
end NQueensComp.NPC