Lemma 34 — a 1-in-3 assignment gives a solution of M₅
ProvedNQueensComp.NPC.lemma_34gadgetsn-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 34. If the truth assignment solves , then is a solution to , where is the red solution if and the blue solution otherwise, and are chosen as in the proof of Lemma 33 according to which variable of is true:
Together with Lemma 35 this gives the bijection between solutions behind Theorem 36.
Formalization Note is given by its set of true variables. The clause-gadget parts are the explicit table of the definition module (clauseSols), which writes out the three cases of the proof of Lemma 33.
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
- encoding: S₄(G¹_c), S₄(G²_c), S₄(G³_c) “set as in the proof of Lemma 33”, which gives the case of vᵢ red and omits the cases vⱼ, vₖ red (p. 836) → the explicit table
clauseSolsfor all three cases; reason: the omitted cases are derived by the rules the proof states; the table was checked by enumerating all solutions of M₅,c
Preamble
import Mathlib import Definitions.Def_NQueensComp_NPC_Reductions
Formal statement
namespace NQueensComp.NPC
/-- Lemma 34, p. 836: if the truth assignment with true set `T` solves `M₆`, then `S₅` is a
solution to `M₅` (Definition 31), where `S₄(G⁰ᵢ)` is the red solution iff `vᵢ ∈ T` and the blue one
otherwise, and `S₄(G¹_c), S₄(G²_c), S₄(G³_c)` are as in the proof of Lemma 33. -/
theorem lemma_34 (cs : Inst6) (hcs : Inst6Valid cs) (T : Finset ℕ) (hT : Inst6IsSol cs T) :
Inst5IsSol (def31 cs) (lemma34_map cs T) := by sorry
end NQueensComp.NPC
Source
Gent, Jefferson & Nightingale, Complexity of n-Queens Completion, J. Artif. Intell. Res. 59 (2017), p. 836, Lemma 34 (with the proof of Lemma 33, p. 835)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.