Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 23, instance level — Definition 20 preserves validity and the number of solutions

Proved
NQueensComp.NPC.theorem_23_instances

by Victorized · Nov 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

n-queensparsimonious-reduction

Let def20\mathrm{def20}def20 be the construction of Definition 20 (corrected: D+D^+D+ ends at 2n−22n-22n−2; the empty family is sent to ⟨1,{0},{0},{},{}⟩\langle 1,\{0\},\{0\},\{\},\{\}\rangle⟨1,{0},{0},{},{}⟩), 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 M5M_5M5​ of Problem 5, def20(M5)\mathrm{def20}(M_5)def20(M5​) is a valid instance of Problem 4, and the two instances have the same number of solutions:

∣{S:S solves def20(M5)}∣=∣{S:S solves M5}∣.\bigl|\{S : S \text{ solves } \mathrm{def20}(M_5)\}\bigr| = \bigl|\{S : S \text{ solves } M_5\}\bigr|.​{S:S solves def20(M5​)}​=​{S:S solves M5​}​.

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 000, 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).

Preamble
import Mathlib
import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
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
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 831, Theorem 23 (instance-level half)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me