Theorem 23, instance level — Definition 20 preserves validity and the number of solutions
ProvedNQueensComp.NPC.theorem_23_instancesLet be the construction of Definition 20 (corrected: ends at ; the empty family is sent to ), which sends an instance of Problem 5 to an instance of Problem 4.
Claim (instance-level half of Theorem 23, p. 831). For every valid instance of Problem 5, is a valid instance of Problem 4, and the two instances have the same number of solutions:
The paper proves this through Lemmas 21 and 22, 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_23; the other, theorem_23_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 23, instance-level half. -/
theorem theorem_23_instances :
∀ Ms : Inst5, Inst5Valid Ms →
(def20 Ms).Valid ∧
_root_.Set.ncard {S : Finset Queen | (def20 Ms).IsSol S} =
_root_.Set.ncard {Ss : List (Finset Queen) | Inst5IsSol Ms Ss} := by sorry
end NQueensComp.NPC