Lemma 35 — a solution of M₅ gives a 1-in-3 assignment
ProvedNQueensComp.NPC.lemma_35gadgetsn-queensone-in-three-satp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an instance of Restricted 1-in-3-SAT and its image under Definition 31.
Lemma 35. For any solution of :
- each is the red or the blue solution of ;
- the assignment with iff is the red solution (and iff it is the blue solution) is a solution to :
This is the inverse direction of Lemma 34.
Formalization Note sits at position of the family when is the -th smallest variable; 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.