Lemma 33 — M₅,c has exactly three solutions, one for each choice of the red variable gadget
ProvedNQueensComp.NPC.lemma_33gadgetsn-queensone-in-three-satp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an instance of Restricted 1-in-3-SAT and , , one of its clauses. is the family of six Problem 4 gadgets of Definitions 26–28 and 31. Each has a red solution and a blue solution .
Lemma 33. , as an instance of Problem 5, has exactly three solutions:
- in one, takes its red solution and their blue solutions;
- in a second, is red and are blue;
- in the third, is red and are blue.
Thus the clause gadgets force exactly one variable of each clause to be true, which is what makes the reduction from Restricted 1-in-3-SAT parsimonious.
Formalization Note is the list [G⁰ᵢ, G⁰ⱼ, G⁰ₖ, G¹_c, G²_c, G³_c], so positions 0, 1, 2 of a solution are the parts on . The clause is taken inside a fixed instance, because the diagonals depend on the rank of among the clauses of .
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
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC
/-- Lemma 33, p. 835: for a clause `c = c_j = {vᵢ, vⱼ, vₖ}` (`i < j < k`) of an instance `M₆`,
the six-gadget family `M₅,c = [G⁰ᵢ, G⁰ⱼ, G⁰ₖ, G¹_c, G²_c, G³_c]` has exactly three solutions: in
one `G⁰ᵢ` takes its red solution and `G⁰ⱼ, G⁰ₖ` their blue ones; in a second `G⁰ⱼ` is red and
`G⁰ᵢ, G⁰ₖ` blue; in the third `G⁰ₖ` is red and `G⁰ᵢ, G⁰ⱼ` blue. -/
theorem lemma_33 (cs : Inst6) (hcs : Inst6Valid cs) (j : ℕ) (hj : j < cs.length) :
_root_.Set.ncard {Ss : List (Finset Queen) | Inst5IsSol (M5c cs j) Ss} = 3 ∧
(∃ Ss, Inst5IsSol (M5c cs j) Ss ∧
Ss.getD 0 ∅ = redSol (delta cs (clauseVar cs j 0)) ∧
Ss.getD 1 ∅ = blueSol (delta cs (clauseVar cs j 1)) ∧
Ss.getD 2 ∅ = blueSol (delta cs (clauseVar cs j 2))) ∧
(∃ Ss, Inst5IsSol (M5c cs j) Ss ∧
Ss.getD 0 ∅ = blueSol (delta cs (clauseVar cs j 0)) ∧
Ss.getD 1 ∅ = redSol (delta cs (clauseVar cs j 1)) ∧
Ss.getD 2 ∅ = blueSol (delta cs (clauseVar cs j 2))) ∧
(∃ Ss, Inst5IsSol (M5c cs j) Ss ∧
Ss.getD 0 ∅ = blueSol (delta cs (clauseVar cs j 0)) ∧
Ss.getD 1 ∅ = blueSol (delta cs (clauseVar cs j 1)) ∧
Ss.getD 2 ∅ = redSol (delta cs (clauseVar cs j 2))) := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 835, Lemma 33
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.