Theorem 13, instance level — Definition 10 preserves validity and the number of solutions
ProvedNQueensComp.NPC.theorem_13_instancesLet be the construction of Definition 10, which sends an instance of Problem 3 to an instance of Problem 2 (n-Queens Completion).
Claim (instance-level half of Theorem 13, p. 826). For every valid instance of Problem 3, is a valid instance of Problem 2 (n-Queens Completion), and the two instances have the same number of solutions:
The paper proves this through Lemmas 11 and 12, 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_13; the other, theorem_13_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 13, instance-level half. -/
theorem theorem_13_instances :
∀ M : Inst3, M.Valid →
(def10 M).Valid ∧
_root_.Set.ncard {S : Finset Queen | (def10 M).IsSol S} =
_root_.Set.ncard {S : Finset Queen | M.IsSol S} := by sorry
end NQueensComp.NPC