Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 35 — a solution of M₅ gives a 1-in-3 assignment

Proved
NQueensComp.NPC.lemma_35

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

gadgetsn-queensone-in-three-satp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let M6M_6M6​ be an instance of Restricted 1-in-3-SAT and M5M_5M5​ its image under Definition 31.

Lemma 35. For any solution S5={S4(G)∣G∈M5}S_5=\{S_4(G)\mid G\in M_5\}S5​={S4​(G)∣G∈M5​} of M5M_5M5​:

  1. each S4(Gi0)S_4(G^0_i)S4​(Gi0​) is the red or the blue solution of Gi0G^0_iGi0​;
  2. the assignment S6S_6S6​ with S6(vi)=trueS_6(v_i)=\mathrm{true}S6​(vi​)=true iff S4(Gi0)S_4(G^0_i)S4​(Gi0​) is the red solution (and false\mathrm{false}false iff it is the blue solution) is a solution to M6M_6M6​:
S5 solves M5 ⟹ S6 solves M6.S_5\ \text{solves}\ M_5\ \Longrightarrow\ S_6\ \text{solves}\ M_6.S5​ solves M5​ ⟹ S6​ solves M6​.

This is the inverse direction of Lemma 34.

Formalization Note Gv0G^0_{v}Gv0​ sits at position iii of the family when v=viv=v_iv=vi​ is the iii-th smallest variable; S6S_6S6​ is returned as its set of true variables.

Differences from the source:

  • encoding: an instance of Problem 5 is a set M₅ = {M₄,ₐ | 0 ≤ a < |M₅|} and a solution a set S₅ = {S₄,ₐ}; the sum-diagonal condition for any {S₄,ₐ, S₄,b} ⊆ S₅ → an instance is a list [M₄,₀, …, M₄,ₖ₋₁], a solution a list [S₄,₀, …] of the same length, and the sum-diagonal condition is imposed for indices a ≠ b; reason: the paper indexes the family itself; read with a = b the condition would forbid every non-empty solution
  • encoding: V = {vᵢ}, C = {cᵢ}, an arbitrary order of variables and clauses fixed before the reduction (p. 831); a solution is a truth assignment S₆ : V → {true, false} → variables are natural numbers ordered increasingly (vᵢ is the i-th smallest element of V); the clauses form a duplicate-free list whose order is the clause order; a solution is the set T ⊆ V of true variables; reason: one admissible choice of the fixed orders; assignments V → {true, false} correspond bijectively to subsets T ⊆ V, so counts agree
  • reading: Lemma 35 presupposes that each S₄(G⁰ᵢ) is the red or the blue solution (“S₆ is well defined since …”) → stated as the first conjunct of the conclusion; reason: makes the presupposition of the statement explicit; G⁰ has exactly these two solutions (p. 831)
Preamble
import Mathlib
import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC

/-- Lemma 35, p. 836: for any solution `S₅` of `M₅` (Definition 31), each `S₄(G⁰ᵢ)` is the red or
the blue solution, and the assignment `S₆(vᵢ) = true` iff `S₄(G⁰ᵢ)` is the red solution solves
`M₆`. -/
theorem lemma_35 (cs : Inst6) (hcs : Inst6Valid cs) (Ss : List (Finset Queen))
    (hS : Inst5IsSol (def31 cs) Ss) :
    (∀ v ∈ vars cs, Ss.getD (varIdx cs v) ∅ = redSol (delta cs v) ∨
      Ss.getD (varIdx cs v) ∅ = blueSol (delta cs v)) ∧
    Inst6IsSol cs (lemma35_map cs Ss) := by sorry

end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 836, Lemma 35
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

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